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 then
    • return 0

  • If node is leaf node then
    • temp = 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

Latest Source Code:
Github: BinaryTreeToSumTreeTransformer.java

Output:

     10       
  / \   
 /   \  
 -2   6   
/ \ / \ 
8 -4 7 5 
                
Sum Tree 
   20       
  / \   
 /   \  
 4   12   
/ \ / \ 
0 0 0 0