Skip to main content

Check if a given Binary Tree is Sumtree

Here given code implementation process.

/*
    C Program 
    Check if a given Binary Tree is Sumtree
*/
#include <stdio.h>
#include <stdlib.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};

//This is creating a binary tree node and return new node
struct Node *get_node(int data)
{
	// Create dynamic node
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//Set data and pointer values
		new_node->data = data;
		new_node->left = NULL;
		new_node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return new_node;
}

//Display pre order elements
void print_preorder(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		print_preorder(node->left);
		print_preorder(node->right);
	}
}

//Handles the request of display the element of tree 
void print_tree(struct Node *root)
{
	if (root == NULL)
	{
		return;
	}
	// Display tree elements in three formats
	printf("\n Preorder : ");
	print_preorder(root);
	printf("\n");
}

//Determine whether given binary tree is subtree or not
int check_sum_tree(struct Node *node, int *status)
{
	if (node == NULL || *status == 0)
	{
		return 0;
	}
	else if (node->left == NULL && node->right == NULL)
	{
		return node->data;
	}
	else
	{
		//recursively calculate sum of left and right subtree
		int a = check_sum_tree(node->left, status);
		int b = check_sum_tree(node->right, status);
		if ( *status == 1)
		{
			if ((a + b) == node->data)
			{
				return (a + b) *2;
			}
			else
			{
				// violation of subtree sum 
				*status = 0;
			}
		}
		return 0;
	}
}

// Handles the request of to find sum tree exist in binary tree
void is_sum_tree(struct Node *root)
{
	if (root == NULL)
	{
		return;
	}
	else
	{
		int status = 1;
		print_tree(root);
		check_sum_tree(root, & status);
		if (status == 1)
		{
			printf(" Is Sum Tree \n");
		}
		else
		{
			printf(" Is Not Sum Tree \n");
		}
	}
}
int main()
{
	struct Node *root1 = NULL;
	/* 
	Constructing binary tree
	-----------------------
	         96
	        /  \
	       /    \
	     37     11
	     / \    /  \
	    18  1  5    6
	     \
	      9
	     /  \
	    3    6
	*/
	root1 = get_node(96);
	root1->left = get_node(37);
	root1->left->right = get_node(1);
	root1->right = get_node(11);
	root1->right->right = get_node(6);
	root1->right->left = get_node(5);
	root1->left->left = get_node(18);
	root1->left->left->right = get_node(9);
	root1->left->left->right->right = get_node(6);
	root1->left->left->right->left = get_node(3);
	is_sum_tree(root1);
	struct Node *root2 = NULL;
	/* 
	Constructing binary tree
	-----------------------
	         36
	        /  \
	       /    \
	      2      17
	     / \    /  \
	    1   1  5    6
	   
	*/
	root2 = get_node(36);
	root2->left = get_node(2);
	root2->left->right = get_node(1);
	root2->right = get_node(17);
	root2->right->right = get_node(6);
	root2->right->left = get_node(5);
	root2->left->left = get_node(1);
	/*
	When subtree sum is not equal to parent node
	----------------------------------------
	  17 => problem here
	 /  \
	5    6
	*/
	is_sum_tree(root2);
	return 0;
}

Output

 Preorder :   96  37  18  9  3  6  1  11  5  6
 Is Sum Tree

 Preorder :   36  2  1  1  17  5  6
 Is Not Sum Tree
/*
    Java Program 
    Check if a given Binary Tree is Sumtree
*/
// Binary Tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class Result
{
	public boolean status;
	public Result()
	{
		this.status = true;
	}
}
//Define Binary Tree 
public class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		//Set root of tree
		this.root = null;
	}
	//Display pre order elements
	public void print_preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print(" " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	//Handles the request of display the element of tree 
	public void print_tree(Node root)
	{
		if (root == null)
		{
			return;
		}
		// Display tree elements in three formats
		System.out.print("\n Preorder : ");
		print_preorder(root);
		System.out.print("\n");
	}
	//Determine whether given binary tree is subtree or not
	public int check_sum_tree(Node node, Result output)
	{
		if (node == null || output.status == false)
		{
			return 0;
		}
		else if (node.left == null && node.right == null)
		{
			return node.data;
		}
		else
		{
			//recursively calculate sum of left and right subtree
			int a = check_sum_tree(node.left, output);
			int b = check_sum_tree(node.right, output);
			if (output.status == true)
			{
				if ((a + b) == node.data)
				{
					return (a + b) * 2;
				}
				else
				{
					// violation of subtree sum 
					output.status = false;
				}
			}
			return 0;
		}
	}
	// Handles the request of to find sum tree exist in binary tree
	public void is_sum_tree()
	{
		if (this.root == null)
		{
			return;
		}
		else
		{
			Result output = new Result();
			this.print_tree(this.root);
			this.check_sum_tree(this.root, output);
			if (output.status == true)
			{
				System.out.print(" Is Sum Tree \n");
			}
			else
			{
				System.out.print(" Is Not Sum Tree \n");
			}
		}
	}
	public static void main(String[] args)
	{
		//Create tree object
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = new BinaryTree();
		/*  
		Constructing binary tree
		-----------------------
		         96
		        /  \
		       /    \
		     37     11
		     / \    /  \
		    18  1  5    6
		     \
		      9
		     /  \
		    3    6
		*/
		tree1.root = new Node(96);
		tree1.root.left = new Node(37);
		tree1.root.left.right = new Node(1);
		tree1.root.right = new Node(11);
		tree1.root.right.right = new Node(6);
		tree1.root.right.left = new Node(5);
		tree1.root.left.left = new Node(18);
		tree1.root.left.left.right = new Node(9);
		tree1.root.left.left.right.right = new Node(6);
		tree1.root.left.left.right.left = new Node(3);
		tree1.is_sum_tree();
		/*  
		Constructing binary tree
		-----------------------
		     36
		    /  \
		   /    \
		  2      17
		 / \    /  \
		1   1  5    6
		   
		*/
		tree2.root = new Node(36);
		tree2.root.left = new Node(2);
		tree2.root.left.right = new Node(1);
		tree2.root.right = new Node(17);
		tree2.root.right.right = new Node(6);
		tree2.root.right.left = new Node(5);
		tree2.root.left.left = new Node(1);
		/*
		When subtree sum is not equal to parent node
		----------------------------------------
		  17 => problem here
		 /  \
		5    6

		*/
		tree2.is_sum_tree();
	}
}

Output

 Preorder :  96 37 18 9 3 6 1 11 5 6
 Is Sum Tree

 Preorder :  36 2 1 1 17 5 6
 Is Not Sum Tree
// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program 
    Check if a given Binary Tree is Sumtree
*/

//  Binary Tree node
class Node
{
	public: 
    int data;
	Node *left;
	Node *right;
	Node(int data)
	{
		//  Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class Result
{
	public: 
    bool status;
	Result()
	{
		this->status = true;
	}
};
// Define Binary Tree
class BinaryTree
{
	public: Node *root;
	BinaryTree()
	{
		// Set root of tree
		this->root = NULL;
	}
	// Display pre order elements
	void print_preorder(Node *node)
	{
		if (node != NULL)
		{
			// Print node value
			cout << " " << node->data;
			this->print_preorder(node->left);
			this->print_preorder(node->right);
		}
	}
	// Handles the request of display the element of tree
	void print_tree(Node *root)
	{
		if (root == NULL)
		{
			return;
		}
		//  Display tree elements in three formats
		cout << "\n Preorder : ";
		this->print_preorder(root);
		cout << "\n";
	}
	// Determine whether given binary tree is subtree or not
	int check_sum_tree(Node *node, Result *output)
	{
		if (node == NULL || output->status == false)
		{
			return 0;
		}
		else if (node->left == NULL && node->right == NULL)
		{
			return node->data;
		}
		else
		{
			// recursively calculate sum of left and right subtree
			int a = this->check_sum_tree(node->left, output);
			int b = this->check_sum_tree(node->right, output);
			if (output->status == true)
			{
				if ((a + b) == node->data)
				{
					return (a + b) *2;
				}
				else
				{
					//  violation of subtree sum
					output->status = false;
				}
			}
			return 0;
		}
	}
	//  Handles the request of to find sum tree exist in binary tree
	void is_sum_tree()
	{
		if (this->root == NULL)
		{
			return;
		}
		else
		{
			Result *output = new Result();
			this->print_tree(this->root);
			this->check_sum_tree(this->root, output);
			if (output->status == true)
			{
				cout << " Is Sum Tree \n";
			}
			else
			{
				cout << " Is Not Sum Tree \n";
			}
		}
	}
};
int main()
{
	// Create tree object
	BinaryTree tree1 = BinaryTree();
	BinaryTree tree2 = BinaryTree();
	/*
			Constructing binary tree
			-----------------------
			         96
			        /  \
			       /    \
			     37     11
			     / \    /  \
			    18  1  5    6
			     \
			      9
			     /  \
			    3    6
			*/
	tree1.root = new Node(96);
	tree1.root->left = new Node(37);
	tree1.root->left->right = new Node(1);
	tree1.root->right = new Node(11);
	tree1.root->right->right = new Node(6);
	tree1.root->right->left = new Node(5);
	tree1.root->left->left = new Node(18);
	tree1.root->left->left->right = new Node(9);
	tree1.root->left->left->right->right = new Node(6);
	tree1.root->left->left->right->left = new Node(3);
	tree1.is_sum_tree();
	/*
			Constructing binary tree
			-----------------------
			     36
			    /  \
			   /    \
			  2      17
			 / \    /  \
			1   1  5    6
			   
			*/
	tree2.root = new Node(36);
	tree2.root->left = new Node(2);
	tree2.root->left->right = new Node(1);
	tree2.root->right = new Node(17);
	tree2.root->right->right = new Node(6);
	tree2.root->right->left = new Node(5);
	tree2.root->left->left = new Node(1);
	/*
			When subtree sum is not equal to parent node
			----------------------------------------
			  17 => problem here
			 /  \
			5    6

			*/
	tree2.is_sum_tree();
	return 0;
}

Output

 Preorder :  96 37 18 9 3 6 1 11 5 6
 Is Sum Tree

 Preorder :  36 2 1 1 17 5 6
 Is Not Sum Tree
// Include namespace system
using System;

/*
    C# Program 
    Check if a given Binary Tree is Sumtree
*/

//  Binary Tree node
public class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class Result
{
	public Boolean status;
	public Result()
	{
		this.status = true;
	}
}
// Define Binary Tree
public class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	// Display pre order elements
	public void print_preorder(Node node)
	{
		if (node != null)
		{
			// Print node value
			Console.Write(" " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	// Handles the request of display the element of tree
	public void print_tree(Node root)
	{
		if (root == null)
		{
			return;
		}
		//  Display tree elements in three formats
		Console.Write("\n Preorder : ");
		print_preorder(root);
		Console.Write("\n");
	}
	// Determine whether given binary tree is subtree or not
	public int check_sum_tree(Node node, Result output)
	{
		if (node == null || output.status == false)
		{
			return 0;
		}
		else if (node.left == null && node.right == null)
		{
			return node.data;
		}
		else
		{
			// recursively calculate sum of left and right subtree
			int a = check_sum_tree(node.left, output);
			int b = check_sum_tree(node.right, output);
			if (output.status == true)
			{
				if ((a + b) == node.data)
				{
					return (a + b) * 2;
				}
				else
				{
					//  violation of subtree sum
					output.status = false;
				}
			}
			return 0;
		}
	}
	//  Handles the request of to find sum tree exist in binary tree
	public void is_sum_tree()
	{
		if (this.root == null)
		{
			return;
		}
		else
		{
			Result output = new Result();
			this.print_tree(this.root);
			this.check_sum_tree(this.root, output);
			if (output.status == true)
			{
				Console.Write(" Is Sum Tree \n");
			}
			else
			{
				Console.Write(" Is Not Sum Tree \n");
			}
		}
	}
	public static void Main(String[] args)
	{
		// Create tree object
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = new BinaryTree();
		/*  
				Constructing binary tree
				-----------------------
				         96
				        /  \
				       /    \
				     37     11
				     / \    /  \
				    18  1  5    6
				     \
				      9
				     /  \
				    3    6
				*/
		tree1.root = new Node(96);
		tree1.root.left = new Node(37);
		tree1.root.left.right = new Node(1);
		tree1.root.right = new Node(11);
		tree1.root.right.right = new Node(6);
		tree1.root.right.left = new Node(5);
		tree1.root.left.left = new Node(18);
		tree1.root.left.left.right = new Node(9);
		tree1.root.left.left.right.right = new Node(6);
		tree1.root.left.left.right.left = new Node(3);
		tree1.is_sum_tree();
		/*  
				Constructing binary tree
				-----------------------
				     36
				    /  \
				   /    \
				  2      17
				 / \    /  \
				1   1  5    6
				   
				*/
		tree2.root = new Node(36);
		tree2.root.left = new Node(2);
		tree2.root.left.right = new Node(1);
		tree2.root.right = new Node(17);
		tree2.root.right.right = new Node(6);
		tree2.root.right.left = new Node(5);
		tree2.root.left.left = new Node(1);
		/*
				When subtree sum is not equal to parent node
				----------------------------------------
				  17 => problem here
				 /  \
				5    6

				*/
		tree2.is_sum_tree();
	}
}

Output

 Preorder :  96 37 18 9 3 6 1 11 5 6
 Is Sum Tree

 Preorder :  36 2 1 1 17 5 6
 Is Not Sum Tree
<?php
/*
    Php Program 
    Check if a given Binary Tree is Sumtree
*/

//  Binary Tree node
class Node
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		//  Set node value
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class Result
{
	public $status;

	function __construct()
	{
		$this->status = true;
	}
}
// Define Binary Tree
class BinaryTree
{
	public $root;

	function __construct()
	{
		// Set root of tree
		$this->root = null;
	}
	// Display pre order elements
	public	function print_preorder($node)
	{
		if ($node != null)
		{
			// Print node value
			echo " ". $node->data;
			$this->print_preorder($node->left);
			$this->print_preorder($node->right);
		}
	}
	// Handles the request of display the element of tree
	public	function print_tree($root)
	{
		if ($root == null)
		{
			return;
		}
		//  Display tree elements in three formats
		echo "\n Preorder : ";
		$this->print_preorder($root);
		echo "\n";
	}
	// Determine whether given binary tree is subtree or not
	public	function check_sum_tree($node, $output)
	{
		if ($node == null || $output->status == false)
		{
			return 0;
		}
		else if ($node->left == null && $node->right == null)
		{
			return $node->data;
		}
		else
		{
			// recursively calculate sum of left and right subtree
			$a = $this->check_sum_tree($node->left, $output);
			$b = $this->check_sum_tree($node->right, $output);
			if ($output->status == true)
			{
				if (($a + $b) == $node->data)
				{
					return ($a + $b) * 2;
				}
				else
				{
					//  violation of subtree sum
					$output->status = false;
				}
			}
			return 0;
		}
	}
	//  Handles the request of to find sum tree exist in binary tree
	public	function is_sum_tree()
	{
		if ($this->root == null)
		{
			return;
		}
		else
		{
			$output = new Result();
			$this->print_tree($this->root);
			$this->check_sum_tree($this->root, $output);
			if ($output->status == true)
			{
				echo " Is Sum Tree \n";
			}
			else
			{
				echo " Is Not Sum Tree \n";
			}
		}
	}
}

function main()
{
	// Create tree object
	$tree1 = new BinaryTree();
	$tree2 = new BinaryTree();
	/*  
			Constructing binary tree
			-----------------------
			         96
			        /  \
			       /    \
			     37     11
			     / \    /  \
			    18  1  5    6
			     \
			      9
			     /  \
			    3    6
	*/
	$tree1->root = new Node(96);
	$tree1->root->left = new Node(37);
	$tree1->root->left->right = new Node(1);
	$tree1->root->right = new Node(11);
	$tree1->root->right->right = new Node(6);
	$tree1->root->right->left = new Node(5);
	$tree1->root->left->left = new Node(18);
	$tree1->root->left->left->right = new Node(9);
	$tree1->root->left->left->right->right = new Node(6);
	$tree1->root->left->left->right->left = new Node(3);
	$tree1->is_sum_tree();
	/*  
			Constructing binary tree
			-----------------------
			     36
			    /  \
			   /    \
			  2      17
			 / \    /  \
			1   1  5    6
			   
	*/
	$tree2->root = new Node(36);
	$tree2->root->left = new Node(2);
	$tree2->root->left->right = new Node(1);
	$tree2->root->right = new Node(17);
	$tree2->root->right->right = new Node(6);
	$tree2->root->right->left = new Node(5);
	$tree2->root->left->left = new Node(1);
	/*
			When subtree sum is not equal to parent node
			----------------------------------------
			  17 => problem here
			 /  \
			5    6

	*/
	$tree2->is_sum_tree();
}
main();

Output

 Preorder :  96 37 18 9 3 6 1 11 5 6
 Is Sum Tree

 Preorder :  36 2 1 1 17 5 6
 Is Not Sum Tree
/*
    Node Js Program 
    Check if a given Binary Tree is Sumtree
*/

//  Binary Tree node
class Node
{
	constructor(data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class Result
{
	constructor()
	{
		this.status = true;
	}
}
// Define Binary Tree
class BinaryTree
{
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	// Display pre order elements
	print_preorder(node)
	{
		if (node != null)
		{
			// Print node value
			process.stdout.write(" " + node.data);
			this.print_preorder(node.left);
			this.print_preorder(node.right);
		}
	}
	// Handles the request of display the element of tree
	print_tree(root)
	{
		if (root == null)
		{
			return;
		}
		//  Display tree elements in three formats
		process.stdout.write("\n Preorder : ");
		this.print_preorder(root);
		process.stdout.write("\n");
	}
	// Determine whether given binary tree is subtree or not
	check_sum_tree(node, output)
	{
		if (node == null || output.status == false)
		{
			return 0;
		}
		else if (node.left == null && node.right == null)
		{
			return node.data;
		}
		else
		{
			// recursively calculate sum of left and right subtree
			var a = this.check_sum_tree(node.left, output);
			var b = this.check_sum_tree(node.right, output);
			if (output.status == true)
			{
				if ((a + b) == node.data)
				{
					return (a + b) * 2;
				}
				else
				{
					//  violation of subtree sum
					output.status = false;
				}
			}
			return 0;
		}
	}
	//  Handles the request of to find sum tree exist in binary tree
	is_sum_tree()
	{
		if (this.root == null)
		{
			return;
		}
		else
		{
			var output = new Result();
			this.print_tree(this.root);
			this.check_sum_tree(this.root, output);
			if (output.status == true)
			{
				process.stdout.write(" Is Sum Tree \n");
			}
			else
			{
				process.stdout.write(" Is Not Sum Tree \n");
			}
		}
	}
}

function main()
{
	// Create tree object
	var tree1 = new BinaryTree();
	var tree2 = new BinaryTree();
	/*  
			Constructing binary tree
			-----------------------
			         96
			        /  \
			       /    \
			     37     11
			     / \    /  \
			    18  1  5    6
			     \
			      9
			     /  \
			    3    6
			*/
	tree1.root = new Node(96);
	tree1.root.left = new Node(37);
	tree1.root.left.right = new Node(1);
	tree1.root.right = new Node(11);
	tree1.root.right.right = new Node(6);
	tree1.root.right.left = new Node(5);
	tree1.root.left.left = new Node(18);
	tree1.root.left.left.right = new Node(9);
	tree1.root.left.left.right.right = new Node(6);
	tree1.root.left.left.right.left = new Node(3);
	tree1.is_sum_tree();
	/*  
			Constructing binary tree
			-----------------------
			     36
			    /  \
			   /    \
			  2      17
			 / \    /  \
			1   1  5    6
			   
			*/
	tree2.root = new Node(36);
	tree2.root.left = new Node(2);
	tree2.root.left.right = new Node(1);
	tree2.root.right = new Node(17);
	tree2.root.right.right = new Node(6);
	tree2.root.right.left = new Node(5);
	tree2.root.left.left = new Node(1);
	/*
			When subtree sum is not equal to parent node
			----------------------------------------
			  17 => problem here
			 /  \
			5    6

			*/
	tree2.is_sum_tree();
}
main();

Output

 Preorder :  96 37 18 9 3 6 1 11 5 6
 Is Sum Tree

 Preorder :  36 2 1 1 17 5 6
 Is Not Sum Tree
#     Python 3 Program 
#     Check if a given Binary Tree is Sumtree

#  Binary Tree node
class Node :
	
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class Result :
	
	def __init__(self) :
		self.status = True
	

# Define Binary Tree 
class BinaryTree :
	
	def __init__(self) :
		# Set root of tree
		self.root = None
	
	# Display pre order elements
	def print_preorder(self, node) :
		if (node != None) :
			# Print node value
			print(" ", node.data, end = "")
			self.print_preorder(node.left)
			self.print_preorder(node.right)
		
	
	# Handles the request of display the element of tree 
	def print_tree(self, root) :
		if (root == None) :
			return
		
		#  Display tree elements in three formats
		print("\n Preorder : ", end = "")
		self.print_preorder(root)
		print("\n", end = "")
	
	# Determine whether given binary tree is subtree or not
	def check_sum_tree(self, node, output) :
		if (node == None or output.status == False) :
			return 0
		
		elif(node.left == None and node.right == None) :
			return node.data
		else :
			# recursively calculate sum of left and right subtree
			a = self.check_sum_tree(node.left, output)
			b = self.check_sum_tree(node.right, output)
			if (output.status == True) :
				if ((a + b) == node.data) :
					return (a + b) * 2
				else :
					#  violation of subtree sum 
					output.status = False
				
			
			return 0
		
	
	#  Handles the request of to find sum tree exist in binary tree
	def is_sum_tree(self) :
		if (self.root == None) :
			return
		else :
			output = Result()
			self.print_tree(self.root)
			self.check_sum_tree(self.root, output)
			if (output.status == True) :
				print(" Is Sum Tree \n", end = "")
			else :
				print(" Is Not Sum Tree \n", end = "")
			
		
	

def main() :
	# Create tree object
	tree1 = BinaryTree()
	tree2 = BinaryTree()
	#   
	# 		Constructing binary tree
	# 		-----------------------
	# 		         96
	# 		        /  \
	# 		       /    \
	# 		     37     11
	# 		     / \    /  \
	# 		    18  1  5    6
	# 		     \
	# 		      9
	# 		     /  \
	# 		    3    6
	# 		
	
	tree1.root = Node(96)
	tree1.root.left = Node(37)
	tree1.root.left.right = Node(1)
	tree1.root.right = Node(11)
	tree1.root.right.right = Node(6)
	tree1.root.right.left = Node(5)
	tree1.root.left.left = Node(18)
	tree1.root.left.left.right = Node(9)
	tree1.root.left.left.right.right = Node(6)
	tree1.root.left.left.right.left = Node(3)
	tree1.is_sum_tree()
	#   
	# 		Constructing binary tree
	# 		-----------------------
	# 		     36
	# 		    /  \
	# 		   /    \
	# 		  2      17
	# 		 / \    /  \
	# 		1   1  5    6
	# 		   
	# 		
	
	tree2.root = Node(36)
	tree2.root.left = Node(2)
	tree2.root.left.right = Node(1)
	tree2.root.right = Node(17)
	tree2.root.right.right = Node(6)
	tree2.root.right.left = Node(5)
	tree2.root.left.left = Node(1)
	# 
	# 		When subtree sum is not equal to parent node
	# 		----------------------------------------
	# 		  17 => problem here
	# 		 /  \
	# 		5    6
	# 		
	
	tree2.is_sum_tree()

if __name__ == "__main__": main()

Output

 Preorder :   96  37  18  9  3  6  1  11  5  6
 Is Sum Tree

 Preorder :   36  2  1  1  17  5  6
 Is Not Sum Tree
#  Ruby Program 
#  Check if a given Binary Tree is Sumtree

#  Binary Tree node
class Node  
	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class Result  
	# Define the accessor and reader of class Result  
	attr_reader :status
	attr_accessor :status
 
	
	def initialize() 
		self.status = true
	end

end

# Define Binary Tree 
class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root
 
	
	def initialize() 
		# Set root of tree
		self.root = nil
	end

	# Display pre order elements
	def print_preorder(node) 
		if (node != nil) 
			# Print node value
			print(" ", node.data)
			self.print_preorder(node.left)
			self.print_preorder(node.right)
		end

	end

	# Handles the request of display the element of tree 
	def print_tree(root) 
		if (root == nil) 
			return
		end

		#  Display tree elements in three formats
		print("\n Preorder : ")
		self.print_preorder(root)
		print("\n")
	end

	# Determine whether given binary tree is subtree or not
	def check_sum_tree(node, output) 
		if (node == nil || output.status == false) 
			return 0
		elsif(node.left == nil && node.right == nil) 
			return node.data
		else 
			# recursively calculate sum of left and right subtree
			a = self.check_sum_tree(node.left, output)
			b = self.check_sum_tree(node.right, output)
			if (output.status == true) 
				if ((a + b) == node.data) 
					return (a + b) * 2
				else 
					#  violation of subtree sum 
					output.status = false
				end

			end

			return 0
		end

	end

	#  Handles the request of to find sum tree exist in binary tree
	def is_sum_tree() 
		if (self.root == nil) 
			return
		else 
			output = Result.new()
			self.print_tree(self.root)
			self.check_sum_tree(self.root, output)
			if (output.status == true) 
				print(" Is Sum Tree \n")
			else 
				print(" Is Not Sum Tree \n")
			end

		end

	end

end

def main() 
	# Create tree object
	tree1 = BinaryTree.new()
	tree2 = BinaryTree.new()
	#   
	# 		Constructing binary tree
	# 		-----------------------
	# 		         96
	# 		        /  \
	# 		       /    \
	# 		     37     11
	# 		     / \    /  \
	# 		    18  1  5    6
	# 		     \
	# 		      9
	# 		     /  \
	# 		    3    6
	# 		
	
	tree1.root = Node.new(96)
	tree1.root.left = Node.new(37)
	tree1.root.left.right = Node.new(1)
	tree1.root.right = Node.new(11)
	tree1.root.right.right = Node.new(6)
	tree1.root.right.left = Node.new(5)
	tree1.root.left.left = Node.new(18)
	tree1.root.left.left.right = Node.new(9)
	tree1.root.left.left.right.right = Node.new(6)
	tree1.root.left.left.right.left = Node.new(3)
	tree1.is_sum_tree()
	#   
	# 		Constructing binary tree
	# 		-----------------------
	# 		     36
	# 		    /  \
	# 		   /    \
	# 		  2      17
	# 		 / \    /  \
	# 		1   1  5    6
	# 		   
	# 		
	
	tree2.root = Node.new(36)
	tree2.root.left = Node.new(2)
	tree2.root.left.right = Node.new(1)
	tree2.root.right = Node.new(17)
	tree2.root.right.right = Node.new(6)
	tree2.root.right.left = Node.new(5)
	tree2.root.left.left = Node.new(1)
	# 
	# 		When subtree sum is not equal to parent node
	# 		----------------------------------------
	# 		  17 => problem here
	# 		 /  \
	# 		5    6
	# 		
	
	tree2.is_sum_tree()
end

main()

Output

 Preorder :  96 37 18 9 3 6 1 11 5 6
 Is Sum Tree 

 Preorder :  36 2 1 1 17 5 6
 Is Not Sum Tree 

/*
    Scala Program 
    Check if a given Binary Tree is Sumtree
*/

//  Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class Result(var status: Boolean)
{
	def this()
	{
		this(true);
	}
}
// Define Binary Tree
class BinaryTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	// Display pre order elements
	def print_preorder(node: Node): Unit = {
		if (node != null)
		{
			// Print node value
			print(" " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	// Handles the request of display the element of tree
	def print_tree(root: Node): Unit = {
		if (root == null)
		{
			return;
		}
		//  Display tree elements in three formats
		print("\n Preorder : ");
		print_preorder(root);
		print("\n");
	}
	// Determine whether given binary tree is subtree or not
	def check_sum_tree(node: Node, output: Result): Int = {
		if (node == null || output.status == false)
		{
			return 0;
		}
		else if (node.left == null && node.right == null)
		{
			return node.data;
		}
		else
		{
			// recursively calculate sum of left and right subtree
			var a: Int = check_sum_tree(node.left, output);
			var b: Int = check_sum_tree(node.right, output);
			if (output.status == true)
			{
				if ((a + b) == node.data)
				{
					return (a + b) * 2;
				}
				else
				{
					//  violation of subtree sum
					output.status = false;
				}
			}
			return 0;
		}
	}
	//  Handles the request of to find sum tree exist in binary tree
	def is_sum_tree(): Unit = {
		if (this.root == null)
		{
			return;
		}
		else
		{
			var output: Result = new Result();
			this.print_tree(this.root);
			this.check_sum_tree(this.root, output);
			if (output.status == true)
			{
				print(" Is Sum Tree \n");
			}
			else
			{
				print(" Is Not Sum Tree \n");
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create tree object
		var tree1: BinaryTree = new BinaryTree();
		var tree2: BinaryTree = new BinaryTree();
		/*  
				Constructing binary tree
				-----------------------
				         96
				        /  \
				       /    \
				     37     11
				     / \    /  \
				    18  1  5    6
				     \
				      9
				     /  \
				    3    6
				*/
		tree1.root = new Node(96);
		tree1.root.left = new Node(37);
		tree1.root.left.right = new Node(1);
		tree1.root.right = new Node(11);
		tree1.root.right.right = new Node(6);
		tree1.root.right.left = new Node(5);
		tree1.root.left.left = new Node(18);
		tree1.root.left.left.right = new Node(9);
		tree1.root.left.left.right.right = new Node(6);
		tree1.root.left.left.right.left = new Node(3);
		tree1.is_sum_tree();
		/*  
				Constructing binary tree
				-----------------------
				     36
				    /  \
				   /    \
				  2      17
				 / \    /  \
				1   1  5    6
				   
				*/
		tree2.root = new Node(36);
		tree2.root.left = new Node(2);
		tree2.root.left.right = new Node(1);
		tree2.root.right = new Node(17);
		tree2.root.right.right = new Node(6);
		tree2.root.right.left = new Node(5);
		tree2.root.left.left = new Node(1);
		/*
				When subtree sum is not equal to parent node
				----------------------------------------
				  17 => problem here
				 /  \
				5    6

				*/
		tree2.is_sum_tree();
	}
}

Output

 Preorder :  96 37 18 9 3 6 1 11 5 6
 Is Sum Tree

 Preorder :  36 2 1 1 17 5 6
 Is Not Sum Tree
/*
    Swift 4 Program 
    Check if a given Binary Tree is Sumtree
*/

//  Binary Tree node
class Node
{
	var data: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		//  Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class Result
{
	var status: Bool;
	init()
	{
		self.status = true;
	}
}
// Define Binary Tree
class BinaryTree
{
	var root: Node? ;
	init()
	{
		// Set root of tree
		self.root = nil;
	}
	// Display pre order elements
	func print_preorder(_ node: Node? )
	{
		if (node != nil)
		{
			// Print node value
			print(" ", node!.data, terminator: "");
			self.print_preorder(node!.left);
			self.print_preorder(node!.right);
		}
	}
	// Handles the request of display the element of tree
	func print_tree(_ root: Node? )
	{
		if (root == nil)
		{
			return;
		}
		//  Display tree elements in three formats
		print("\n Preorder : ", terminator: "");
		self.print_preorder(root);
		print("\n", terminator: "");
	}
	// Determine whether given binary tree is subtree or not
	func check_sum_tree(_ node: Node? , _ output : Result? )->Int
	{
		if (node == nil || output!.status == false)
		{
			return 0;
		}
		else if (node!.left == nil && node!.right == nil)
		{
			return node!.data;
		}
		else
		{
			// recursively calculate sum of left and right subtree
			let a: Int = self.check_sum_tree(node!.left, output);
			let b: Int = self.check_sum_tree(node!.right, output);
			if (output!.status == true)
			{
				if ((a + b) == node!.data)
				{
					return (a + b) * 2;
				}
				else
				{
					//  violation of subtree sum
					output!.status = false;
				}
			}
			return 0;
		}
	}
	//  Handles the request of to find sum tree exist in binary tree
	func is_sum_tree()
	{
		if (self.root == nil)
		{
			return;
		}
		else
		{
			let output: Result? = Result();
			self.print_tree(self.root);
			let _ = self.check_sum_tree(self.root, output);
			if (output!.status == true)
			{
				print(" Is Sum Tree \n", terminator: "");
			}
			else
			{
				print(" Is Not Sum Tree \n", terminator: "");
			}
		}
	}
}
func main()
{
	// Create tree object
	let tree1: BinaryTree = BinaryTree();
	let tree2: BinaryTree = BinaryTree();
	/*  
		Constructing binary tree
		-----------------------
		         96
		        /  \
		       /    \
		     37     11
		     / \    /  \
		    18  1  5    6
		     \
		      9
		     /  \
		    3    6
		*/
	tree1.root = Node(96);
	tree1.root!.left = Node(37);
	tree1.root!.left!.right = Node(1);
	tree1.root!.right = Node(11);
	tree1.root!.right!.right = Node(6);
	tree1.root!.right!.left = Node(5);
	tree1.root!.left!.left = Node(18);
	tree1.root!.left!.left!.right = Node(9);
	tree1.root!.left!.left!.right!.right = Node(6);
	tree1.root!.left!.left!.right!.left = Node(3);
	tree1.is_sum_tree();
	/*  
		Constructing binary tree
		-----------------------
		     36
		    /  \
		   /    \
		  2      17
		 / \    /  \
		1   1  5    6
		   
		*/
	tree2.root = Node(36);
	tree2.root!.left = Node(2);
	tree2.root!.left!.right = Node(1);
	tree2.root!.right = Node(17);
	tree2.root!.right!.right = Node(6);
	tree2.root!.right!.left = Node(5);
	tree2.root!.left!.left = Node(1);
	/*
		When subtree sum is not equal to parent node
		----------------------------------------
		  17 => problem here
		 /  \
		5    6

		*/
	tree2.is_sum_tree();
}
main();

Output

 Preorder :   96  37  18  9  3  6  1  11  5  6
 Is Sum Tree

 Preorder :   36  2  1  1  17  5  6
 Is Not Sum Tree
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment