Check if a given Binary Tree is SumTree in Java

By Aditya Goyal

In this tutorial, we are going to learn to check if a Binary Tree is a Sum Tree or not in Java. It is a Tree in which the root node is equal to the sum of it’s left and right subtree. In this, each of the node value should be equal to it’s left and right subtree.

So now, we are going to traverse in a postorder and check if the non-leaf node is equal to the sum of its subtrees. So, after checking this condition we will return if the tree is sum tree or not.

Code: –

class Node  
{ 
    int val; 
    Node leftNode; 
    Node rightNode; 
    Node(int dat)  
    { 
        val = dat; 
        leftNode = null;
        rightNode= null;
    } 
} 
   
class Main 
{ 
    Node root; 
    //Calculate Sum of value in tree using recursion
    int sumVal(Node node)  
    { 
        // If empty it is 0;
        if (node == null) {
            return 0;
        }
        return sumVal(node.leftNode) + node.val + sumVal(node.rightNode); 
    }
    // Function to check if node is equal to left right subtree 
    boolean checkTree(Node node)  
    { 
        int leftsum, rightsum; 
        //If node is NULL or without subtree.
        if ((node == null) || (node.leftNode == null && node.rightNode == null)){
            return true;
        }
        // Sum of left and right subtree
        leftsum = sumVal(node.leftNode); 
        rightsum = sumVal(node.rightNode); 
        // If the node and its left right suntree agree with the condition 
        if ((node.val == leftsum+rightsum) && checkTree(node.leftNode) && checkTree(node.rightNode) ){
            return true;
        } 
        return false; 
    } 
    public static void main(String args[])  
    { 
        Main BinaryTree = new Main(); 
        BinaryTree.root = new Node(30); 
        BinaryTree.root.leftNode = new Node(10); 
        BinaryTree.root.rightNode = new Node(5); 
        BinaryTree.root.leftNode.leftNode = new Node(5); 
        BinaryTree.root.leftNode.rightNode = new Node(5); 
        BinaryTree.root.rightNode.rightNode = new Node(5); 
   
        if (BinaryTree.checkTree(BinaryTree.root)){
            System.out.println("SumTree");
        } 
        else{
            System.out.println("Not a SumTree");
        }
    } 
}

Output: –

SumTree

So, this Binary Tree is a Sum Tree as the sum of each node is equal to sum of the left-right subtree.

Also Read: –

Postorder tree Traversal using Recursion in Java