Transform to Sum Tree
Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0.
Algorithm:
- Traverse tree in postOrder
- If
node is null
thenreturn 0
- If
node is leaf node
thentemp = node.data
node.data = 0
return temp
- leftSum = Recursive call with left subtree (i.e. node->left)
rightSum = Recursive call with righ subtree (i.e. node->right)
temp = node.data
node.data = leftSum + rightSum
return node.data + temp
- If
Latest Source Code:
Github: BinaryTreeToSumTreeTransformer.java
Output:
10 / \ / \ -2 6 / \ / \ 8 -4 7 5 Sum Tree 20 / \ / \ 4 12 / \ / \ 0 0 0 0