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 –

Download   Run Complete Code

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.

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Thanks for reading.

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 🙂

Leave a Reply

newest oldest most voted
Notify of

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

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

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