Convert binary tree to its sum tree in-place

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.

Given Binary Tree
Sum tree with all integer nodes
Sum tree of given binary tree.

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 O(n). The complete code for this problem is as shown below.

Hence is the sum tree explanation with complexity O(n). If you know any better solution or find any problem in code, please let readers know by commenting here below. Cheers!.