Check if a given Binary Tree is SumTree in C++

In this tutorial, we are going to learn how to check for a SumTree in a Binary Tree using C++. If the value of each node in a Binary Tree is equal to the sum of all the nodes present in its left and right subtrees then the tree is called a SumTree.

Example of a SumTree:

trees chart

If the root of a subtree in a SumTree has at least one child then the sum of the values of all nodes in the subtree is equal to twice the value of the root. In the above example, as the binary tree is a SumTree the sum of all the nodes is equal to twice the value of the root.

20*2 = 20 + 3 + 7 + 1 + 2 + 3 + 4

Using the above observation we will implement a recursive function that checks if a given Binary Tree is a SumTree.

Implementing a function to check if a Binary Tree is Sum Tree

Recursive Function

isSumTree(root)

  1. If the node is empty or if the node is a leaf node return True.
  2. Assume that the left subtree and right subtree are SumTrees and find the sum of the nodes in the left subtree and the right subtree.
  3. Check if the current subtree is a SumTree.
  4. Verify if the left subtree and right subtree are SumTrees by making the recursive function call on them.
  5. If the above two conditions are satisfied return True or else return False.

 

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node* left;
    Node* right;
    Node(int val){
        data = val;
        left = NULL,right = NULL;
    }
};
int sumOfSubTree(Node* node){
    if(node == NULL){
        return 0;
    }
    // Checking if the node is a leaf node
    else if(node->left == NULL && node->right == NULL){
        return node->data;
    }
    else{
        return 2*(node->data);
    }
}
bool isSumTree(Node* node){
    if(node == NULL || 
                    (node->left == NULL && node->right == NULL)){
        return true;
    }
    int l,r;

    /* Assume that the left and right subtrees are
       SumTrees and get the sum of nodes in left and 
       right subtrees respectively */
    l = sumOfSubTree(node->left);
    r = sumOfSubTree(node->right);

    /* Check if the current subtree is a SumTree
       and also verify if the left and right subtrees
       are also SumTrees */
    if(node->data == (l+r) && isSumTree(node->left) && 
                                 isSumTree(node->right)){
        return true;
    }
    else{
        return false;
    }   
}
int main(){
    struct Node* root  = new Node(20);
    root->left         = new Node(3); 
    root->right        = new Node(7); 
    root->left->left   = new Node(1); 
    root->left->right  = new Node(2); 
    root->right->left  = new Node(3);
    root->right->right = new Node(4);
    if(isSumTree(root)){
        cout<<"The given Binary Tree is a SumTree"<<endl;
    }
    else{
        cout<<"The given Binary Tree is not a SumTree"<<endl;
    }
}

Output:

The given Binary Tree is a SumTree

sumOfSubTree() function takes the root of subtree as an argument and returns the sum of nodes in the subtree.

Time Complexity: O(n)

 

We hope you got a clear idea of how to check if a given Binary tree is SumTree in C++.

Leave a Reply