Question 6 (7 marks)
Consider the following binary search tree and a variable t which contains a pointer to the node containing the key 20 (i.e. the root node):
Based on the above, answer the following questions:
Give the keys that would be examined, in the order that they are examined, when searching for the value 17 starting from the root node.
Show the order that key values would be be displayed if we performed a level-order traversal of the tree.
The above tree is perfectly balanced (i.e. every node has the same number of nodes in its left and right subtrees) and has a height of 4 (the number of nodes in the longest path from the root to a leaf). Give a formula for the number of nodes in a perfectly balanced tree of height n.
If the following function was applied to the original tree above (i.e. with root node containing key 20):
t = rotateL(t);
what would be the new value in the root node, and what would be the values in its immediate left and right children?
If the following function was applied to the original tree above (i.e. with root node containing key 20):
t = deleteRoot(t);
what would be the new value in the root node, and what would be the values in its immediate left and right children?
Use the definitions of rotateL() and deleteRoot() are in the Algorithms Almanac.
Type the answer to this question into the file called q6.txt and submit it using the command:
$ submit q6
The above command will make a copy of q6.txt as your answer for this question.