Sum Binary Tree or Not
Mohd Talib
1456
Binary TreeInterview

Problem Statement

Given a Binary Tree. Return true if, for every node X in the tree other than the leaves, its value is equal to the sum of its left subtree's value and its right subtree's value. Else return false. An empty tree is also a Sum Tree as the sum of an empty tree can be considered to be 0. A leaf node is also considered a Sum Tree.

Java Implementation

class Solution
{
	public boolean isSumTree(TreeNode root){
        return isSumT(root) != -1;
	}
    private long isSumT(Node root) {
		if(root == null){
          return 0;
        }
        
        long left = isSumT(root.left);
        long right = isSumT(root.right);
        
        if(root.left == null && root.right == null){
            return root.val;
        }
        
        if(left ==-1  || right == -1 || root.val != left + right){
          return -1;
        }
        return left + right + root.val;
      
	}
}
Comments (1)