A binary tree with integer nodes is given, we aim to convert this binary tree to its sum tree in-place.
A Sum Tree is a binary tree in which the value of the current node is a sum of data of all its descendent nodes data.
Let’s see below the binary tree and its sum tree example.
Here, in the above example, the left child in the sum tree is “7” which is a sum of its children -7 & 14.
Let’s check the below formula to solve this problem
N=sum(L, R) // Where node is not NULL
N=0 // while node is NULL.
N --> Current node in sum tree
L --> Left node of N in sum tree
R --> Right node of N in sum tree
Finally, lets see the code for this problem.
// Convert sum tree in-place.
int sumTree(struct Node *root)
{
if(root == NULL)
return 0;
int nodeVal = root->data;
root->data = sumTree(root->left) + sumTree(root->right);
return root->data + nodeVal;
}
This solution has complexity of . The complete code for this problem is as shown below.
Hence is the sum tree explanation with complexity . If you know any better solution or find any problem in code, please let readers know by commenting here below. Cheers!.