81 / \ 20 100 / \ 16 65
25 / \ 10 30 / \ 26 50
i Rep[i] i Rep[i] i Rep[i] i Rep[i] 1 1 1 ___ 1 ___ 1 ___ 2 2 2 ___ 2 ___ 2 ___ c(1,5) c(5,2) c(5,4) 3 3 --------> 3 ___ --------> 3 ___ --------> 3 ___ 4 4 4 ___ 4 ___ 4 ___ 5 5 5 ___ 5 ___ 5 ___
struct TreeNode { int data; TreeNode* left; TreeNode* right; }; typedef TreeNode* Tree;
Use the types TreeNode and Tree of the previous problem. Suppose that function node(x,lft,rgt) is available, where node(x,lft,rgt) returns a pointer to a newly allocated node holding data x, left subtree lft and right subtree rgt. (Do not write this function, just use it.)
Write a function removeMin(t) that returns the tree that would result from removing the smallest value from tree t, but that does not alter tree t. If t is empty, then removeMin(t) should return an empty tree. For example, if t is the tree
81 / \ 20 100 \ 65 / \ 50 70then removeMin(t) should return the following tree, without altering tree t.
81 / \ 65 100 / \ 50 70Do not rebalance the tree. The new tree that you construct can share subtrees with t, as long as it does not change the subtrees.
Tree removeMin(Tree t) {