ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Check if binary tree is a sum tree

prodevelopertutorial March 30, 2020

In this tutorial we shall check if the tree is a sum tree or not.

 

Problem Statement:

You are given the root node of a binary tree. You need to check if that tree is a sum tree or not.

 

Example:

Consider the binary tree given below:

 

Check if binary tree is a sum tree

In the above image, it is a sum tree.

 

What is a sum tree?

A tree will be called as sum tree, if the parent node value is equal to the sum of it’s left sub tree and right sub tree.

 

For 1 and 2 parent node value is 3. That is the sum of 1 + 2

For 4 and 5 parent node value is 9, that is the sum of 4 + 5

 

For the root node value is 24, i.e it’s sum of left sub tree 3 + 2 + 1 = 6

and sum of right sub tree i.e 9 + 4 + 5 = 18.

 

By looking at the image, we can infer that, only the leaf node will not satisfy this condition.

But all the internal nodes need to satisfy this condition.

 

Solution in C++

#include <iostream>
#include <stack>
#include <map>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};



int check_is_sum_tree(Node* node) 
{ 
    // base case: empty tree
    if (node == NULL)
        return 0;

    // leaf node
    if (node->left == NULL && node->right == NULL)
        return node->data;


    if (node->data == check_is_sum_tree(node->left) + check_is_sum_tree(node->right))
        return 2*node->data;

    return INT_MIN;
}  
  
  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);


    if(check_is_sum_tree(root) != INT_MIN)
    {
        cout<<"It is a Sum tree"<<endl;
    } else {
        cout<<"It is not a sum tree"<<endl;
    }

    return 0;  
}

 

Output:

It is not a sum tree

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io