Consider a procedure that inserts a sequence of elements in a binary search tree. input: A...

 

Transcribed Image Text:

Consider a procedure that inserts a sequence of elements in a binary search tree. input: A list of integers a of size n local: A binary search tree t without self-balancing t - 0; foreach x E a do |t+insert(t, x); end // Iterate over all elements of a in order For each of the points below, does there exist an input sequence of any arbitrary length that produces a tree as described below? If it exists, give a strategy to construct a sequence of arbitrary length and provide an example with length n = 7. If it does not exist, give an argument. (a) A tree completely skewed to the right. (b) A tree completely skewed to the left. (c) A perfectly balanced tree. (d) A tree whose subtree at the left of the root has exactly 2 elements. (e) A tree with exactly one element. [4 marks] [4 marks] [4 marks] [4 marks] [4 marks] Consider a procedure that inserts a sequence of elements in a binary search tree. input: A list of integers a of size n local: A binary search tree t without self-balancing t - 0; foreach x E a do |t+insert(t, x); end // Iterate over all elements of a in order For each of the points below, does there exist an input sequence of any arbitrary length that produces a tree as described below? If it exists, give a strategy to construct a sequence of arbitrary length and provide an example with length n = 7. If it does not exist, give an argument. (a) A tree completely skewed to the right. (b) A tree completely skewed to the left. (c) A perfectly balanced tree. (d) A tree whose subtree at the left of the root has exactly 2 elements. (e) A tree with exactly one element. [4 marks] [4 marks] [4 marks] [4 marks] [4 marks]

Answer rating: 100% (QA)

a A tree completely skewd to the right means that every element in the tree has only right child chi... View the full answer