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.

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Recursive function to in-place convert the given binary tree to its // sum tree by traversing the tree in postorder manner int convertToSumTree(Node *root) { // base case: tree is empty if (root == nullptr) return 0; // recursively convert left and right subtree first before // processing the root node int left = convertToSumTree(root->left); int right = convertToSumTree(root->right); // stores current value of root node int old = root->data; // update root to sum of its left and right subtree root->data = left + right; // return the updated value plus old value. It is equal to // sum of all elements present in sub-tree rooted at root node return root->data + old; } |

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

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.