Sum Tree

Write a function that returns true if the given Binary Tree is SumTree else false.

A SumTree is a Binary Tree where value of every node x is equal to sum of nodes present in its left subtree and right subtree of x. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.

Sum Tree Example:

           103
         /    \
      100      3
   /   \     /   \
  40   60  1      2

Algorithm:

• Create a dummy class to hold result
• Traverse tree in post order
  • If node is null then return true
  • If node is leaf node then return true
  • Recursively call for left sub tree
  • Recursively call for right sub tree
  • Check node sum of left child and right child
  • Return node.data = left.data + right.data && isLeftSubTreeSumTree && isRightSubTreeSumTree

Latest Source Code:
Github: SumBinaryTree.java

Output:

   13       
  / \   
 /   \  
 10   3   
/ \ / \ 
4 6 2 1 
                
Is sum tree: true
------------------------------------------------------------
       100               
      / \       
     /   \      
    /     \     
   /       \    
   80       20       
  / \     /     
 /   \   /      
 60   20   20       
/ \     / \     
35 25     7 13     
                                
Is sum tree: true