Check if a given Binary Tree is Sum Tree
Last Updated :
19 Jul, 2023
Write a function that returns true if the given Binary Tree is SumTree else false. A SumTree is a Binary Tree where the value of a node is equal to the sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and the sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.
Following is an example of SumTree.
26
/ \
10 3
/ \ \
4 6 3
Method 1 (Simple)
Get the sum of nodes in the left subtree and right subtree. Check if the sum calculated is equal to the root’s data. Also, recursively check if the left and right subtrees are SumTrees.
C++
#include <iostream>
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 isSumTree( 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) &&
isSumTree(node->left) &&
isSumTree(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(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if (isSumTree(root))
cout << "The given tree is a SumTree " ;
else
cout << "The given tree is not a SumTree " ;
getchar ();
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
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 isSumTree( 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)&&
isSumTree(node->left) &&
isSumTree(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(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if (isSumTree(root))
printf ( "The given tree is a SumTree." );
else
printf ( "The given tree is not a SumTree." );
getchar ();
return 0;
}
|
Java
import java.io.*;
class Node
{
int data;
Node left, right, nextRight;
Node( int item)
{
data = item;
left = right = null ;
}
}
class BinaryTree {
public static Node root;
static int sum(Node node)
{
if (node == null )
{
return 0 ;
}
return (sum(node.left) + node.data+sum(node.right));
}
static int isSumTree(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) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0 )
{
return 1 ;
}
return 0 ;
}
public static void main (String[] args)
{
BinaryTree tree= new BinaryTree();
tree.root= new Node( 26 );
tree.root.left= new Node( 10 );
tree.root.right= new Node( 3 );
tree.root.left.left= new Node( 4 );
tree.root.left.right= new Node( 6 );
tree.root.right.right= new Node( 3 );
if (isSumTree(root) != 0 )
{
System.out.println( "The given tree is a SumTree" );
}
else
{
System.out.println( "The given tree is not a SumTree" );
}
}
}
|
Python3
class node:
def __init__( self , x):
self .data = x
self .left = None
self .right = None
def sum (root):
if (root = = None ):
return 0
return ( sum (root.left) +
root.data +
sum (root.right))
def isSumTree(node):
if (node = = None or
(node.left = = None and
node.right = = None )):
return 1
ls = sum (node.left)
rs = sum (node.right)
if ((node.data = = ls + rs) and
isSumTree(node.left) and
isSumTree(node.right)):
return 1
return 0
if __name__ = = '__main__' :
root = node( 26 )
root.left = node( 10 )
root.right = node( 3 )
root.left.left = node( 4 )
root.left.right = node( 6 )
root.right.right = node( 3 )
if (isSumTree(root)):
print ( "The given tree is a SumTree " )
else :
print ( "The given tree is not a SumTree " )
|
C#
using System;
public class Node
{
public int data;
public Node left, right, nextRight;
public Node( int item)
{
data = item;
left = right = null ;
}
}
class BinaryTree {
public Node root;
int sum(Node node)
{
if (node == null )
{
return 0;
}
return (sum(node.left) + node.data+sum(node.right));
}
int isSumTree(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) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0)
{
return 1;
}
return 0;
}
public static void Main( string [] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(26);
tree.root.left = new Node(10);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(6);
tree.root.right.right = new Node(3);
if (tree.isSumTree(tree.root) != 0)
{
Console.WriteLine( "The given tree is a SumTree" );
}
else
{
Console.WriteLine( "The given tree is not a SumTree" );
}
}
}
|
Javascript
<script>
class Node
{
constructor(x) {
this .data = x;
this .left = null ;
this .right = null ;
}
}
let root;
function sum(node)
{
if (node == null )
{
return 0;
}
return (sum(node.left) + node.data+sum(node.right));
}
function isSumTree(node)
{
let 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) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0)
{
return 1;
}
return 0;
}
root = new Node(26)
root.left= new Node(10)
root.right = new Node(3)
root.left.left = new Node(4)
root.left.right = new Node(6)
root.right.right = new Node(3)
if (isSumTree(root) != 0)
{
document.write( "The given tree is a SumTree" );
}
else
{
document.write( "The given tree is not a SumTree" );
}
</script>
|
Output
The given tree is a SumTree
Time Complexity: O(n2) in the worst case. The worst-case occurs for a skewed tree.
Auxiliary Space: O(n) for stack space
Method 2:
Method 1 uses sum() to get the sum of nodes in left and right subtrees. This method uses the following rules to get the sum directly.
1) If the node is a leaf node then the sum of the subtree rooted with this node is equal to the value of this node.
2) If the node is not a leaf node then the sum of the subtree rooted with this node is twice the value of this node (Assuming that the tree rooted with this node is SumTree).
C++
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
node* left;
node* right;
};
int isLeaf(node *node)
{
if (node == NULL)
return 0;
if (node->left == NULL && node->right == NULL)
return 1;
return 0;
}
int isSumTree(node* node)
{
int ls;
int rs;
if (node == NULL || isLeaf(node))
return 1;
if ( isSumTree(node->left) && isSumTree(node->right))
{
if (node->left == NULL)
ls = 0;
else if (isLeaf(node->left))
ls = node->left->data;
else
ls = 2 * (node->left->data);
if (node->right == NULL)
rs = 0;
else if (isLeaf(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(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if (isSumTree(root))
cout << "The given tree is a SumTree " ;
else
cout << "The given tree is not a SumTree " ;
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
int isLeaf( struct node *node)
{
if (node == NULL)
return 0;
if (node->left == NULL && node->right == NULL)
return 1;
return 0;
}
int isSumTree( struct node* node)
{
int ls;
int rs;
if (node == NULL || isLeaf(node))
return 1;
if ( isSumTree(node->left) && isSumTree(node->right))
{
if (node->left == NULL)
ls = 0;
else if (isLeaf(node->left))
ls = node->left->data;
else
ls = 2*(node->left->data);
if (node->right == NULL)
rs = 0;
else if (isLeaf(node->right))
rs = node->right->data;
else
rs = 2*(node->right->data);
return (node->data == ls + rs);
}
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(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if (isSumTree(root))
printf ( "The given tree is a SumTree " );
else
printf ( "The given tree is not a SumTree " );
getchar ();
return 0;
}
|
Java
class Node
{
int data;
Node left, right, nextRight;
Node( int item)
{
data = item;
left = right = nextRight = null ;
}
}
class BinaryTree
{
Node root;
int isLeaf(Node node)
{
if (node == null )
return 0 ;
if (node.left == null && node.right == null )
return 1 ;
return 0 ;
}
int isSumTree(Node node)
{
int ls;
int rs;
if (node == null || isLeaf(node) == 1 )
return 1 ;
if (isSumTree(node.left) != 0 && isSumTree(node.right) != 0 )
{
if (node.left == null )
ls = 0 ;
else if (isLeaf(node.left) != 0 )
ls = node.left.data;
else
ls = 2 * (node.left.data);
if (node.right == null )
rs = 0 ;
else if (isLeaf(node.right) != 0 )
rs = node.right.data;
else
rs = 2 * (node.right.data);
if ((node.data == rs + ls))
return 1 ;
else
return 0 ;
}
return 0 ;
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node( 26 );
tree.root.left = new Node( 10 );
tree.root.right = new Node( 3 );
tree.root.left.left = new Node( 4 );
tree.root.left.right = new Node( 6 );
tree.root.right.right = new Node( 3 );
if (tree.isSumTree(tree.root) != 0 )
System.out.println( "The given tree is a SumTree" );
else
System.out.println( "The given tree is not a SumTree" );
}
}
|
Python3
class node:
def __init__( self , x):
self .data = x
self .left = None
self .right = None
def isLeaf(node):
if (node = = None ):
return 0
if (node.left = = None and node.right = = None ):
return 1
return 0
def sum (root):
if (root = = None ):
return 0
return ( sum (root.left) +
root.data +
sum (root.right))
def isSumTree(node):
if (node = = None or isLeaf(node)):
return 1
if (isSumTree(node.left) and isSumTree(node.right)):
if (node.left = = None ):
ls = 0
elif (isLeaf(node.left)):
ls = node.left.data
else :
ls = 2 * (node.left.data)
if (node.right = = None ):
rs = 0
elif (isLeaf(node.right)):
rs = node.right.data
else :
rs = 2 * (node.right.data)
return (node.data = = ls + rs)
return 0
if __name__ = = '__main__' :
root = node( 26 )
root.left = node( 10 )
root.right = node( 3 )
root.left.left = node( 4 )
root.left.right = node( 6 )
root.right.right = node( 3 )
if (isSumTree(root)):
print ( "The given tree is a SumTree " )
else :
print ( "The given tree is not a SumTree " )
|
C#
using System;
public class Node
{
public int data;
public Node left, right, nextRight;
public Node( int d)
{
data = d;
left = right = nextRight = null ;
}
}
public class BinaryTree{
public static Node root;
public int isLeaf(Node node)
{
if (node == null )
return 0;
if (node.left == null &&
node.right == null )
return 1;
return 0;
}
public int isSumTree(Node node)
{
int ls;
int rs;
if (node == null || isLeaf(node) == 1)
return 1;
if (isSumTree(node.left) != 0 &&
isSumTree(node.right) != 0)
{
if (node.left == null )
ls = 0;
else if (isLeaf(node.left) != 0)
ls = node.left.data;
else
ls = 2 * (node.left.data);
if (node.right == null )
rs = 0;
else if (isLeaf(node.right) != 0)
rs = node.right.data;
else
rs = 2 * (node.right.data);
if ((node.data == rs + ls))
return 1;
else
return 0;
}
return 0;
}
static public void Main()
{
BinaryTree tree = new BinaryTree();
BinaryTree.root = new Node(26);
BinaryTree.root.left = new Node(10);
BinaryTree.root.right = new Node(3);
BinaryTree.root.left.left = new Node(4);
BinaryTree.root.left.right = new Node(6);
BinaryTree.root.right.right = new Node(3);
if (tree.isSumTree(BinaryTree.root) != 0)
{
Console.WriteLine( "The given tree is a SumTree" );
}
else
{
Console.WriteLine( "The given tree is " +
"not a SumTree" );
}
}
}
|
Javascript
<script>
class Node
{
constructor(item) {
this .data = item;
this .left = null ;
this .right = null ;
this .nextRight = null ;
}
}
let root;
function isLeaf(node)
{
if (node == null )
return 0;
if (node.left == null && node.right == null )
return 1;
return 0;
}
function isSumTree(node)
{
let ls;
let rs;
if (node == null || isLeaf(node) == 1)
return 1;
if (isSumTree(node.left) != 0 && isSumTree(node.right) != 0)
{
if (node.left == null )
ls = 0;
else if (isLeaf(node.left) != 0)
ls = node.left.data;
else
ls = 2 * (node.left.data);
if (node.right == null )
rs = 0;
else if (isLeaf(node.right) != 0)
rs = node.right.data;
else
rs = 2 * (node.right.data);
if ((node.data == rs + ls))
return 1;
else
return 0;
}
return 0;
}
root = new Node(26);
root.left = new Node(10);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(6);
root.right.right = new Node(3);
if (isSumTree(root) != 0)
document.write( "The given tree is a SumTree" );
else
document.write( "The given tree is not a SumTree" );
</script>
|
Output
The given tree is a SumTree
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 3
- Similar to postorder traversal iteratively find the sum in each step
- Return left + right + current data if left + right is equal to current node data
- Else return -1
C++14
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
node* left;
node* right;
};
int isLeaf(node *node)
{
if (node == NULL)
return 0;
if (node->left == NULL && node->right == NULL)
return 1;
return 0;
}
int isSumTree(node* node)
{
if (node == NULL)
return 0;
int ls;
int rs;
ls = isSumTree(node->left);
if (ls == -1)
return -1;
rs = isSumTree(node->right);
if (rs == -1)
return -1;
if (isLeaf(node) || ls + rs == node->data)
return ls + rs + node->data;
else
return -1;
}
node* newNode( int data)
{
node* node1 = new node();
node1->data = data;
node1->left = NULL;
node1->right = NULL;
return (node1);
}
int main()
{
node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
int total = isSumTree(root);
if (total != -1 && total == 2*(root->data))
cout<< "Sum Tree" ;
else
cout<< "No sum Tree" ;
return 0;
}
|
C++
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
node* left;
node* right;
};
int isLeaf(node *node)
{
if (node == NULL)
return 0;
if (node->left == NULL && node->right == NULL)
return 1;
return 0;
}
int isSumTree(node* node)
{
if (node == NULL)
return 0;
int ls;
int rs;
ls = isSumTree(node->left);
if (ls == -1)
return -1;
rs = isSumTree(node->right);
if (rs == -1)
return -1;
if (isLeaf(node) || ls + rs == node->data)
return ls + rs + node->data;
else
return -1;
}
node* newNode( int data)
{
node* node1 = new node();
node1->data = data;
node1->left = NULL;
node1->right = NULL;
return (node1);
}
int main()
{
node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
int total = isSumTree(root);
if (total != -1 && total == 2*(root->data))
cout<< "Tree is a Sum Tree" ;
else
cout<< "Given Tree is not sum Tree" ;
return 0;
}
|
Java
import java.util.*;
class GFG
{
static class Node {
int data;
Node left, right;
}
static int isLeaf(Node node)
{
if (node == null )
return 0 ;
if (node.left == null && node.right == null )
return 1 ;
return 0 ;
}
static int isSumTree(Node node)
{
if (node == null )
return 0 ;
int ls;
int rs;
ls = isSumTree(node.left);
if (ls == - 1 )
return - 1 ;
rs = isSumTree(node.right);
if (rs == - 1 )
return - 1 ;
if (isLeaf(node)== 1 || ls + rs == node.data)
return ls + rs + node.data;
else
return - 1 ;
}
static Node newNode( int data)
{
Node node1 = new Node();
node1.data = data;
node1.left = null ;
node1.right = null ;
return (node1);
}
public static void main(String args[])
{
Node root = newNode( 26 );
root.left = newNode( 10 );
root.right = newNode( 3 );
root.left.left = newNode( 4 );
root.left.right = newNode( 6 );
root.right.right = newNode( 3 );
int total = isSumTree(root);
if (total != - 1 && total == 2 *(root.data))
System.out.print( "Tree is a Sum Tree" );
else
System.out.print( "Given Tree is not sum Tree" );
}
}
|
Python3
class node:
def __init__( self , x):
self .data = x
self .left = None
self .right = None
def isLeaf(node):
if (node = = None ):
return 0
if (node.left = = None and node.right = = None ):
return 1
return 0
def isSumTree(node):
if (node = = None ):
return 0
ls = isSumTree(node.left)
if (ls = = - 1 ):
return - 1
rs = isSumTree(node.right)
if (rs = = - 1 ):
return - 1
if (isLeaf(node) or ls + rs = = node.data):
return ls + rs + node.data
else :
return - 1
if __name__ = = '__main__' :
root = node( 26 )
root.left = node( 10 )
root.right = node( 3 )
root.left.left = node( 4 )
root.left.right = node( 6 )
root.right.right = node( 3 )
if (isSumTree(root)):
print ( "The given tree is a SumTree " )
else :
print ( "The given tree is not a SumTree " )
|
C#
using System;
class Program {
public class Node {
public int data;
public Node left, right;
}
static int isLeaf(Node node)
{
if (node == null )
return 0;
if (node.left == null && node.right == null )
return 1;
return 0;
}
static int isSumTree(Node node)
{
if (node == null )
return 0;
int ls;
int rs;
ls = isSumTree(node.left);
if (ls == -1)
return -1;
rs = isSumTree(node.right);
if (rs == -1)
return -1;
if (isLeaf(node) == 1 || ls + rs == node.data)
return ls + rs + node.data;
else
return -1;
}
static Node newNode( int data)
{
Node node1 = new Node();
node1.data = data;
node1.left = null ;
node1.right = null ;
return (node1);
}
static void Main( string [] args)
{
Node root = newNode(26);
root.left = newNode(10);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(6);
root.right.right = newNode(3);
int total = isSumTree(root);
if (total != -1 && total == 2 * (root.data))
Console.WriteLine( "Tree is a Sum Tree" );
else
Console.WriteLine( "Given Tree is not sum Tree" );
}
}
|
Javascript
<script>
class node{
constructor(x){
this .data = x
this .left = null
this .right = null
}
}
function isLeaf(node)
{
if (node == null )
return 0
if (node.left == null && node.right == null )
return 1
return 0
}
function isSumTree(node){
if (node == null )
return 0
let ls = isSumTree(node.left)
if (ls == -1)
return -1
let rs = isSumTree(node.right)
if (rs == -1)
return -1
if (isLeaf(node) || ls + rs == node.data)
return ls + rs + node.data
else
return -1
}
let root = new node(26)
root.left = new node(10)
root.right = new node(3)
root.left.left = new node(4)
root.left.right = new node(6)
root.right.right = new node(3)
if (isSumTree(root))
document.write( "The given tree is a SumTree " )
else
document.write( "The given tree is not a SumTree " )
</script>
|
Time Complexity: O(n), since each element is traversed only once
Auxiliary Space: O(n), due to recursive stack space
Please Login to comment...