Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What are the three laws of recursion?
4.2.
Why is stack used in recursion?
4.3.
What is recursion depth?
5.
Conclusion
Last Updated: Mar 27, 2024

Check if a given Binary Tree is SumTree

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A SumTree is a type of binary tree where the sum of the child subtrees is equal to the parent node. If there is no child node, i.e., a leaf node, that is also a SumTree. An empty binary tree can be considered a SumTree too.

Source

Let’s discuss how to check if a given binary tree is a SumTree or not.

Problem Statement

In this problem, we have to check if a given binary tree is a SumTree.

Sample Examples

Example:

Input: 
The given binary tree is
            32
           /    \
        10      6
       /  \       /  \
     8    2    3    3

Output: The given binary tree is a SumTree.

Explanation: The sum of the left and right subtrees of the root node is equal to the root node (16 = 10 + 6 + 8 + 2 + 3 + 3). Similarly, the sum of the subtrees for nodes 10 and 6 also equals their parent nodes. Therefore, it is a SumTree.

Brute Force Approach

In this approach, we store the root node and then get its subtrees. Check the sum of the subtrees and if it equals the root node. If it is, we continue recursively doing the same for the child nodes, and if it is not, then the binary tree is not a SumTree. If all the non-leaf nodes are equal to the sum of their subtrees, it will be a SumTree.

Steps of Algorithm

  1. First, we check for the case when the binary tree is empty. If it is, we declare it as a SumTree.
  2. We create a sum function that could recursively add all the values of the subtrees.
  3. Take the root node value and pass it through the sum function.
  4. Then check if the value returned by the sum function and the root node is the same. If it is not, the binary tree is not a SumTree. If it is, recursively pass the child nodes through the sum function and compare the values again.
  5. If the sum and parent node values are the same for all the non-leaf nodes, we have a SumTree.

Implementation in C++

#include<bits/stdc++.h>

using namespace std;

struct node {
    int data;
    struct node* left;
    struct node* right;
};

int sum(struct node *root) {
    if (root == NULL)
        return 0;
    return sum(root->left) + root->data +
           sum(root->right);
}

int SumTree(struct node* node) {
    int ls, rs;

    if (node == NULL ||
       (node->left == NULL &&
        node->right == NULL))
        return 1;

   ls = sum(node->left);
   rs = sum(node->right);

    if ((node->data == ls + rs) &&
          SumTree(node->left) &&
          SumTree(node->right))
        return 1;
 
   return 0;
}

struct node* newNode(int data) {
    struct node* node = (struct node*)malloc(
        sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

int main() {
    struct node *root = newNode(32);
    root->left = newNode(10);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(2);
    root->right->right = newNode(3);
    root->right->left = newNode(3);
     
    if (SumTree(root))
        cout << "The given binary tree is a SumTree \n";
    else
        cout << "The given binary tree is not a SumTree \n";

    getchar();
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

The given binary tree is a SumTree

 

Complexity Analysis

Time Complexity: O(N2)

Explanation: In the worst-case scenario, the binary tree will be skewed to one side, so the time complexity is O(N2).

Space Complexity: O(N)

Explanation: In this approach, space is needed for every node, so the space complexity is O(N).

Optimized Approach

In the previous approach, we created a sum function to get the sum of left and right subtrees, but in this approach, we get it through the following process:

  • If the node is a leaf node, the sum of the subtree is just the node's value.
  • In case the node is a non-leaf node, and the tree is a SumTree, the sum of the subtree that the node is a part of would be twice the node's value.

 

So, in this approach, we assume that the given binary tree is a SumTree and check if the assumption holds up.

Steps of Algorithm

  1. For any given node, we check if it is empty or a leaf node. If it is, we can say it fulfils the conditions of being a SumTree. If it is not, we consider its subtrees.
  2. To check if a subtree satisfies the Sumtree conditions, we take its sum. There are three steps to this:
    1. We first check if the root of the subtree is null. In case it is, the sum is obviously zero.
    2. If it is a leaf node, the sum is the value of the given node.
    3. If it is not a leaf node, the sum would be twice the value of the given node.
  3. After doing this for both the left and right subtrees, we add the results and compare them with the root node. In case they are equal, our assumption is valid. In case it is not, the given binary tree is not a SumTree.
  4. We recursively check the same for every node in the given binary tree. If our assumption is valid for all the nodes, the given binary tree is a SumTree, or else it is not.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

struct node {
    int data;
    node* left;
    node* right;
};

int Leaf(node *node) {
    if(node == NULL)
        return 0;
    if(node->left == NULL && node->right == NULL)
        return 1;
    return 0;
}

int SumTree(node* node) {
    int ls;
    int rs;

    if(node == NULL || Leaf(node))
        return 1;
    if(SumTree(node->left) && SumTree(node->right)) {
        if(node->left == NULL)
            ls = 0;
        else if(Leaf(node->left))
            ls = node->left->data;
        else
            ls = 2 * (node->left->data);

        if(node->right == NULL)
            rs = 0;
        else if(Leaf(node->right))
            rs = node->right->data;
        else
            rs = 2 * (node->right->data);

        return(node->data == ls + rs);
    }
    return 0;
}

node* newNode(int data) {
    node* node1 = new node();
    node1->data = data;
    node1->left = NULL;
    node1->right = NULL;
    return(node1);
}

int main() {
    node *root  = newNode(32);
    root->left = newNode(10);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(2);
    root->right->right = newNode(3);
    root->right->left = newNode(3);

    if(SumTree(root))
        cout << "The given binary tree is a SumTree \n";
    else
        cout << "The given binary tree is not a SumTree \n";
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

The given binary tree is a SumTree

 

Complexity Analysis

Time Complexity: O(N)

Explanation: The code will run for every new node, so the time complexity is O(N).

Space Complexity: O(N)

Explanation: In this approach, space is needed for every node, so the space complexity is O(N).

Check out this problem - Root To Leaf Path

Frequently Asked Questions

What are the three laws of recursion?

There are three laws of recursion. A base case is required for a recursive algorithm. A recursive algorithm must change its state and move toward the base case. Recursively, a recursive algorithm must call itself.

Why is stack used in recursion?

The last function must be completed first in recursion. Because stack is a LIFO (Last In First Out) data structure, it is utilised to implement recursion.

What is recursion depth?

The number of layers of activation of a process that exists during the procedure's deepest call is referred to as the depth of recursion.

Conclusion

In conclusion, we discussed different approaches to find if a given binary tree is a SumTree or not. For every approach, we discussed algorithms and complexities. We eventually saw how each of the methods are different from the others.

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass