USA: +1(669)289-8683 
Sign in
Question 510 points
Let T be the root node of a binary search tree. Assume that exactly one node in the tree has a key
value of k. Consider the following recursive algorithm called Prune Tree(T,k) which takes as input the root
node T and removes some nodes from the tree. The root of the new tree is returned by the algorithm.
Prune Tree(T,k)
if T.key = k
return T.left
else if k < T.key
else
x=Prune Tree(T.left, k)
if x + NIL
2.parent = T.parent
return a
T.right Prune Tree(T.right, k)
return T
Complete the following THREE tasks:
1. Execute Prune Tree(T, 29) on the tree below. Draw the tree returned by the algorithm.
17
20
30
26
29
28
32
2. Describe (in english) what the above algorithm is pruning from the input tree T.
3. Update the above algorithm so that it takes as input an interval tree, T, and carries out the same
task using int.low as the key.
