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 –
// 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)
// 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.