Objective: Given a binary tree, write an algorithm to convert it into its Sum tree.

What is Sum tree: Sum tree of a binary tree, is a tree where each node in the converted tree will contains the sum of the left and right sub trees in the original tree.

Example:

Approach:

Recursively calculate the left sum from left sum tree.

Recursively calculate the right sum from right tree.

prepare the return root.data + left sum + right sum.

Update the root data as root.data = left sum + right sum.

update the newRoot = root.

See the code for better understanding.

Complete Code:

Output:

Original Tree: -2 -1 4 5 -6 3 10
Sum tree: 0 2 0 8 0 4 0

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

why do u need to set the newRoot in line13? you are not changing any node pointers in the SumTree method. looks like an unnecessary line of code that really does nothing.