# In-place convert given binary tree to its sum tree

Given a binary tree, in-place convert it to its sum tree. In a sum tree, value at each node is equal to the sum of all elements present in its left and right subtree. The value of an empty node is considered as 0.

For example, We can easily solve this problem by using recursion. The idea is to recursively convert left and right subtree first before processing a node by traversing the tree in postorder fashion. Then for each node, we update the node’s value to sum of all elements present in its left and right subtree and return sum of all elements present in sub-tree rooted at node from the function. The value is calculated at constant time for each node by using return values of left and right subtree.

C++ implementation –

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

I think there is a minor in the above code. It should be

int old = root->data;
root.data = left + right + old;
return root->data;

EDIT: never mind. I had a incorrect understanding of sum tree.