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,

convert a tree to sum tree

 


 

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.
 

Thanks for reading.
 




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz