Question

Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree rooted at v.
(a) Modify the Insert operation (given below) to insert an element so that all the .sum fields of the tree are correct after applying the Insert operation. (Assume that all the .sum fields were correct before the Insert operation.) Your modified algorithm should take the same time as the original Insert operation. Explain your modification and give pseudo-code for the modified algorithm.

function Insert(T,z)

y <-- LocateParent(T,z)

z.parent <-- y

if (y = NIL) then T.root <-- z ;

else if (z.key< y.key) then y.left <-- z

else y.right <-- z

(b) Argue for the correctness of your algorithm. Explain why all the .sum fields are correct after running your modified Insert operation.

(c) Analyze the running time of your modified algorithm in terms of the size n and the height h of the binary search tree.

Answer 1

Answer:

Each time you insert a new node, call the function to adjust the sum.

This method has to be called each time we insert new node to the tree since the sum at all the

parent nodes from the newly inserted node changes when we insert the node.

// toSumTree method will convert the tree into sum tree.

int toSumTree(struct node *node)

{

if(node == NULL)

return 0;

// Store the old value

int old_val = node->data;

// Recursively call for left and right subtrees and store the sum as new value of this node

node->data = toSumTree(node->left) + toSumTree(node->right);

// Return the sum of values of nodes in left and right subtrees and

// old_value of this node

return node->data + old_val;

}

This has the complexity of O(n).

Explanation: