Posted on by Kalkicode
Code Binary Tree

Find largest subtree sum in a tree

Here given code implementation process.

/*
    C Program 
    Find largest subtree sum in a tree
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//This is creating a binary tree node and return this
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 preorder(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		preorder(node->left);
		preorder(node->right);
	}
}
// Returns the max value of two numbers
int max_value(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
// Returns the largest sum of subtree
int largest_sum_subtree(struct Node *node, int *result)
{
	if (node != NULL)
	{
		// Recursively, Find the sum of subtree
		int sum = node->data + largest_sum_subtree(node->left, result) + largest_sum_subtree(node->right, result);
		// Get the max sum of previous and current subtree
		*result = max_value(sum, *result);
		//return the result of current subtree
		return sum;
	}
	else
	{
		return 0;
	}
}
//Handles the request to find largest subtree of max sum
void find_subtree(struct Node *root)
{
	if (root != NULL)
	{
		printf("\n Tree Elements \n");
		//Display tree elements
		preorder(root);
		int result = INT_MIN;
		largest_sum_subtree(root, & result);
		// Display calculated result
		printf("\n Max Sum Subtree : %d\n", result);
	}
	else
	{
		printf("\n Empty Tree \n");
	}
}
int main()
{
	struct Node *root1 = NULL;
	struct Node *root2 = NULL;
	struct Node *root3 = NULL;
	/*
	constructor binary tree
	-----------------
	     6                            
	   /   \    
	 -15    7    
	 / \     \               
	1   3     -8  
	   / \
	  10  8
	       \
	       -1

	-----------------
	First Tree
	*/
	root1 = get_node(6);
	root1->left = get_node(-15);
	root1->left->right = get_node(3);
	root1->left->right->left = get_node(10);
	root1->left->right->right = get_node(8);
	root1->left->right->right->right = get_node(-1);
	root1->left->left = get_node(1);
	root1->right = get_node(7);
	root1->right->right = get_node(-8);
	/*
	constructor binary tree
	-----------------
	    10                            
	   /   \    
	  3     3     
	 /     /  \               
	8     7    8
	       
	-----------------
	Second Tree
	*/
	root2 = get_node(10);
	root2->right = get_node(3);
	root2->right->right = get_node(8);
	root2->right->left = get_node(7);
	root2->left = get_node(3);
	root2->left->left = get_node(8);
	/*
	constructor binary tree
	-----------------
	    20                            
	   /   \    
	  3     3     
	 /        \               
	1          1
	 \        /
	  6     -36  
	        
	-----------------
	Third Tree
	*/
	root3 = get_node(20);
	root3->right = get_node(3);
	root3->right->right = get_node(1);
	root3->right->right->left = get_node(-36);
	root3->left = get_node(3);
	root3->left->left = get_node(1);
	root3->left->left->right = get_node(6);
	//  Test Cases
	/*
	First Tree Result 
	-----------------
	    3  
	   / \
	  10  8
	       \
	        -1
	----------------
	Sum 20
	*/
	find_subtree(root1);
	/*
	Second Tree Result 
	-----------------   
	     10                            
	   /   \    
	  3     3     
	 /     /  \               
	8     7    8
	--------------
	Sum 39
	*/
	find_subtree(root2);
	/*
	Third Tree Result 
	-------------------                          
	      3       
	     /                   
	    1
	     \        
	      6  
	        
	--------------
	Sum 10
	*/
	find_subtree(root3);
	return 0;
}

Output

 Tree Elements
  6  -15  1  3  10  8  -1  7  -8
 Max Sum Subtree : 20

 Tree Elements
  10  3  8  3  7  8
 Max Sum Subtree : 39

 Tree Elements
  20  3  1  6  3  1  -36
 Max Sum Subtree : 10
/*
    Java Program 
    Find largest subtree sum in a tree
*/

// 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;
	}
}
public class BinaryTree
{
	public Node root;
	public int result;
	public BinaryTree()
	{
		//Set initial tree root to null
		this.root = null;
		this.result = 0;
	}
	//Display pre order elements
	public void preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	// Returns the max value of two numbers
	public int max_value(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the largest sum of subtree
	public int largest_sum_subtree(Node node)
	{
		if (node != null)
		{
			// Recursively, Find the sum of subtree
			int sum = node.data + largest_sum_subtree(node.left) + largest_sum_subtree(node.right);
			// Get the max sum of previous and current subtree
			this.result = max_value(sum, this.result);
			//return the result of current subtree
			return sum;
		}
		else
		{
			return 0;
		}
	}
	//Handles the request to find largest subtree of max sum
	public void find_subtree()
	{
		if (this.root != null)
		{
			System.out.print("\n Tree Elements \n");
			//Display tree elements
			preorder(this.root);
			this.result = Integer.MIN_VALUE;
			largest_sum_subtree(this.root);
			// Display calculated result
			System.out.print("\n Max Sum Subtree : " + this.result + "\n");
		}
		else
		{
			System.out.print("\n Empty Tree \n");
		}
	}
	public static void main(String[] args)
	{
		//Create tree objects
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = new BinaryTree();
		BinaryTree tree3 = new BinaryTree();
		/*
		    constructor binary tree
		    -----------------
		         6                            
		       /   \    
		     -15    7    
		     / \     \               
		    1   3     -8  
		       / \
		      10  8
		           \
		           -1

		-----------------
		First Tree
		*/
		tree1.root = new Node(6);
		tree1.root.left = new Node(-15);
		tree1.root.left.right = new Node(3);
		tree1.root.left.right.left = new Node(10);
		tree1.root.left.right.right = new Node(8);
		tree1.root.left.right.right.right = new Node(-1);
		tree1.root.left.left = new Node(1);
		tree1.root.right = new Node(7);
		tree1.root.right.right = new Node(-8);
		/*
		    constructor binary tree
		    -----------------
		        10                            
		       /   \    
		      3     3     
		     /     /  \               
		    8     7    8
		           
		   -----------------
		   Second Tree
		*/
		tree2.root = new Node(10);
		tree2.root.right = new Node(3);
		tree2.root.right.right = new Node(8);
		tree2.root.right.left = new Node(7);
		tree2.root.left = new Node(3);
		tree2.root.left.left = new Node(8);
		/*
		    constructor binary tree
		    -----------------
		        20                            
		       /   \    
		      3     3     
		     /        \               
		    1          1
		     \        /
		      6     -36  
		            
		    -----------------
		    Third Tree
		    */
		tree3.root = new Node(20);
		tree3.root.right = new Node(3);
		tree3.root.right.right = new Node(1);
		tree3.root.right.right.left = new Node(-36);
		tree3.root.left = new Node(3);
		tree3.root.left.left = new Node(1);
		tree3.root.left.left.right = new Node(6);
		//  Test Cases
		/*
		    First Tree Result 
		    -----------------
		        3  
		       / \
		      10  8
		           \
		            -1
		 ----------------
		 Sum 20
		 */
		tree1.find_subtree();
		/*
		    Second Tree Result 
		    -----------------   
		         10                            
		       /   \    
		      3     3     
		     /     /  \               
		    8     7    8
		------------------
		Sum 39
		*/
		tree2.find_subtree();
		/*
		    Third Tree Result 
		    -------------------                          
		          3       
		         /                   
		        1
		         \        
		          6  
		            
		 -----------------
		Sum 10
		*/
		tree3.find_subtree();
	}
}

Output

 Tree Elements
  6  -15  1  3  10  8  -1  7  -8
 Max Sum Subtree : 20

 Tree Elements
  10  3  8  3  7  8
 Max Sum Subtree : 39

 Tree Elements
  20  3  1  6  3  1  -36
 Max Sum Subtree : 10
// Include header file
#include <iostream>
#include<limits.h>
using namespace std;

/*
     C++ Program 
     Find largest subtree sum in a tree
*/

//  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 BinaryTree
{
	public: Node *root;
	int result;
	BinaryTree()
	{
		// Set initial tree root to null
		this->root = NULL;
		this->result = 0;
	}
	// Display pre order elements
	void preorder(Node *node)
	{
		if (node != NULL)
		{
			// Print node value
			cout << "  " << node->data;
			this->preorder(node->left);
			this->preorder(node->right);
		}
	}
	//  Returns the max value of two numbers
	int max_value(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	//  Returns the largest sum of subtree
	int largest_sum_subtree(Node *node)
	{
		if (node != NULL)
		{
			// return the result of current subtree
			//  Recursively, Find the sum of subtree
			int sum = node->data + this->largest_sum_subtree(node->left) + 
              this->largest_sum_subtree(node->right);
			//  Get the max sum of previous and current subtree
			this->result = this->max_value(sum, this->result);
			return sum;
		}
		else
		{
			return 0;
		}
	}
	// Handles the request to find largest subtree of max sum
	void find_subtree()
	{
		if (this->root != NULL)
		{
			cout << "\n Tree Elements \n";
			// Display tree elements
			this->preorder(this->root);
			this->result = INT_MIN;
			this->largest_sum_subtree(this->root);
			//  Display calculated result
			cout << "\n Max Sum Subtree : " << this->result << "\n";
		}
		else
		{
			cout << "\n Empty Tree \n";
		}
	}
};
int main()
{
	// Create tree objects
	BinaryTree tree1 = BinaryTree();
	BinaryTree tree2 = BinaryTree();
	BinaryTree tree3 = BinaryTree();
	/*
	  		    constructor binary tree
	  		    -----------------
	  		         6                            
	  		       /   \    
	  		     -15    7    
	  		     / \     \               
	  		    1   3     -8  
	  		       / \
	  		      10  8
	  		           \
	  		           -1
	  		-----------------
	  		First Tree
	*/
	tree1.root = new Node(6);
	tree1.root->left = new Node(-15);
	tree1.root->left->right = new Node(3);
	tree1.root->left->right->left = new Node(10);
	tree1.root->left->right->right = new Node(8);
	tree1.root->left->right->right->right = new Node(-1);
	tree1.root->left->left = new Node(1);
	tree1.root->right = new Node(7);
	tree1.root->right->right = new Node(-8);
	/*
	  		    constructor binary tree
	  		    -----------------
	  		        10                            
	  		       /   \    
	  		      3     3     
	  		     /     /  \               
	  		    8     7    8
	  		   -----------------
	  		   Second Tree
	*/
	tree2.root = new Node(10);
	tree2.root->right = new Node(3);
	tree2.root->right->right = new Node(8);
	tree2.root->right->left = new Node(7);
	tree2.root->left = new Node(3);
	tree2.root->left->left = new Node(8);
	/*
	  		    constructor binary tree
	  		    -----------------
	  		        20                            
	  		       /   \    
	  		      3     3     
	  		     /        \               
	  		    1          1
	  		     \        /
	  		      6     -36  
	  		    -----------------
	  		    Third Tree
	*/
	tree3.root = new Node(20);
	tree3.root->right = new Node(3);
	tree3.root->right->right = new Node(1);
	tree3.root->right->right->left = new Node(-36);
	tree3.root->left = new Node(3);
	tree3.root->left->left = new Node(1);
	tree3.root->left->left->right = new Node(6);
	/*
	  		    First Tree Result 
	  		    -----------------
	  		        3  
	  		       / \
	  		      10  8
	  		           \
	  		            -1
	  		 ----------------
	  		 Sum 20
	*/
	//   Test Cases
	tree1.find_subtree();
	/*
	  		    Second Tree Result 
	  		    -----------------   
	  		         10                            
	  		       /   \    
	  		      3     3     
	  		     /     /  \               
	  		    8     7    8
	  		------------------
	  		Sum 39
	*/
	tree2.find_subtree();
	/*
	  		    Third Tree Result 
	  		    -------------------                          
	  		          3       
	  		         /                   
	  		        1
	  		         \        
	  		          6  
	  		 -----------------
	  		Sum 10
	*/
	tree3.find_subtree();
	return 0;
}

Output

 Tree Elements
  6  -15  1  3  10  8  -1  7  -8
 Max Sum Subtree : 20

 Tree Elements
  10  3  8  3  7  8
 Max Sum Subtree : 39

 Tree Elements
  20  3  1  6  3  1  -36
 Max Sum Subtree : 10
// Include namespace system
using System;

/*
     C# Program 
     Find largest subtree sum in a tree
*/

//  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 BinaryTree
{
	public Node root;
	public int result;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.result = 0;
	}
	// Display pre order elements
	public void preorder(Node node)
	{
		if (node != null)
		{
			// Print node value
			Console.Write("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//  Returns the max value of two numbers
	public int max_value(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	//  Returns the largest sum of subtree
	public int largest_sum_subtree(Node node)
	{
		if (node != null)
		{
			// return the result of current subtree
			//  Recursively, Find the sum of subtree
			int sum = node.data + largest_sum_subtree(node.left) + largest_sum_subtree(node.right);
			//  Get the max sum of previous and current subtree
			this.result = max_value(sum, this.result);
			return sum;
		}
		else
		{
			return 0;
		}
	}
	// Handles the request to find largest subtree of max sum
	public void find_subtree()
	{
		if (this.root != null)
		{
			Console.Write("\n Tree Elements \n");
			// Display tree elements
			preorder(this.root);
			this.result = int.MinValue;
			largest_sum_subtree(this.root);
			//  Display calculated result
			Console.Write("\n Max Sum Subtree : " + this.result + "\n");
		}
		else
		{
			Console.Write("\n Empty Tree \n");
		}
	}
	public static void Main(String[] args)
	{
		// Create tree objects
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = new BinaryTree();
		BinaryTree tree3 = new BinaryTree();
		/*
		  		    constructor binary tree
		  		    -----------------
		  		         6                            
		  		       /   \    
		  		     -15    7    
		  		     / \     \               
		  		    1   3     -8  
		  		       / \
		  		      10  8
		  		           \
		  		           -1
		  		-----------------
		  		First Tree
		*/
		tree1.root = new Node(6);
		tree1.root.left = new Node(-15);
		tree1.root.left.right = new Node(3);
		tree1.root.left.right.left = new Node(10);
		tree1.root.left.right.right = new Node(8);
		tree1.root.left.right.right.right = new Node(-1);
		tree1.root.left.left = new Node(1);
		tree1.root.right = new Node(7);
		tree1.root.right.right = new Node(-8);
		/*
		  		    constructor binary tree
		  		    -----------------
		  		        10                            
		  		       /   \    
		  		      3     3     
		  		     /     /  \               
		  		    8     7    8
		  		   -----------------
		  		   Second Tree
		*/
		tree2.root = new Node(10);
		tree2.root.right = new Node(3);
		tree2.root.right.right = new Node(8);
		tree2.root.right.left = new Node(7);
		tree2.root.left = new Node(3);
		tree2.root.left.left = new Node(8);
		/*
		  		    constructor binary tree
		  		    -----------------
		  		        20                            
		  		       /   \    
		  		      3     3     
		  		     /        \               
		  		    1          1
		  		     \        /
		  		      6     -36  
		  		    -----------------
		  		    Third Tree
		*/
		tree3.root = new Node(20);
		tree3.root.right = new Node(3);
		tree3.root.right.right = new Node(1);
		tree3.root.right.right.left = new Node(-36);
		tree3.root.left = new Node(3);
		tree3.root.left.left = new Node(1);
		tree3.root.left.left.right = new Node(6);
		/*
		  		    First Tree Result 
		  		    -----------------
		  		        3  
		  		       / \
		  		      10  8
		  		           \
		  		            -1
		  		 ----------------
		  		 Sum 20
		*/
		//   Test Cases
		tree1.find_subtree();
		/*
		  		    Second Tree Result 
		  		    -----------------   
		  		         10                            
		  		       /   \    
		  		      3     3     
		  		     /     /  \               
		  		    8     7    8
		  		------------------
		  		Sum 39
		*/
		tree2.find_subtree();
		/*
		  		    Third Tree Result 
		  		    -------------------                          
		  		          3       
		  		         /                   
		  		        1
		  		         \        
		  		          6  
		  		 -----------------
		  		Sum 10
		*/
		tree3.find_subtree();
	}
}

Output

 Tree Elements
  6  -15  1  3  10  8  -1  7  -8
 Max Sum Subtree : 20

 Tree Elements
  10  3  8  3  7  8
 Max Sum Subtree : 39

 Tree Elements
  20  3  1  6  3  1  -36
 Max Sum Subtree : 10
<?php
/*
     Php Program 
     Find largest subtree sum in a tree
*/

//  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 BinaryTree
{
	public $root;
	public $result;

	function __construct()
	{
		// Set initial tree root to null
		$this->root = null;
		$this->result = 0;
	}
	// Display pre order elements
	public	function preorder($node)
	{
		if ($node != null)
		{
			// Print node value
			echo "  ". $node->data;
			$this->preorder($node->left);
			$this->preorder($node->right);
		}
	}
	//  Returns the max value of two numbers
	public	function max_value($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	//  Returns the largest sum of subtree
	public	function largest_sum_subtree($node)
	{
		if ($node != null)
		{
			// return the result of current subtree
			//  Recursively, Find the sum of subtree
			$sum = $node->data + $this->largest_sum_subtree($node->left) + 
              $this->largest_sum_subtree($node->right);
			//  Get the max sum of previous and current subtree
			$this->result = $this->max_value($sum, $this->result);
			return $sum;
		}
		else
		{
			return 0;
		}
	}
	// Handles the request to find largest subtree of max sum
	public	function find_subtree()
	{
		if ($this->root != null)
		{
			echo "\n Tree Elements \n";
			// Display tree elements
			$this->preorder($this->root);
			$this->result = -PHP_INT_MAX;
			$this->largest_sum_subtree($this->root);
			//  Display calculated result
			echo "\n Max Sum Subtree : ". $this->result ."\n";
		}
		else
		{
			echo "\n Empty Tree \n";
		}
	}
}

function main()
{
	// Create tree objects
	$tree1 = new BinaryTree();
	$tree2 = new BinaryTree();
	$tree3 = new BinaryTree();
	/*
	  		    constructor binary tree
	  		    -----------------
	  		         6                            
	  		       /   \    
	  		     -15    7    
	  		     / \     \               
	  		    1   3     -8  
	  		       / \
	  		      10  8
	  		           \
	  		           -1
	  		-----------------
	  		First Tree
	*/
	$tree1->root = new Node(6);
	$tree1->root->left = new Node(-15);
	$tree1->root->left->right = new Node(3);
	$tree1->root->left->right->left = new Node(10);
	$tree1->root->left->right->right = new Node(8);
	$tree1->root->left->right->right->right = new Node(-1);
	$tree1->root->left->left = new Node(1);
	$tree1->root->right = new Node(7);
	$tree1->root->right->right = new Node(-8);
	/*
	  		    constructor binary tree
	  		    -----------------
	  		        10                            
	  		       /   \    
	  		      3     3     
	  		     /     /  \               
	  		    8     7    8
	  		   -----------------
	  		   Second Tree
	*/
	$tree2->root = new Node(10);
	$tree2->root->right = new Node(3);
	$tree2->root->right->right = new Node(8);
	$tree2->root->right->left = new Node(7);
	$tree2->root->left = new Node(3);
	$tree2->root->left->left = new Node(8);
	/*
	  		    constructor binary tree
	  		    -----------------
	  		        20                            
	  		       /   \    
	  		      3     3     
	  		     /        \               
	  		    1          1
	  		     \        /
	  		      6     -36  
	  		    -----------------
	  		    Third Tree
	*/
	$tree3->root = new Node(20);
	$tree3->root->right = new Node(3);
	$tree3->root->right->right = new Node(1);
	$tree3->root->right->right->left = new Node(-36);
	$tree3->root->left = new Node(3);
	$tree3->root->left->left = new Node(1);
	$tree3->root->left->left->right = new Node(6);
	/*
	  		    First Tree Result 
	  		    -----------------
	  		        3  
	  		       / \
	  		      10  8
	  		           \
	  		            -1
	  		 ----------------
	  		 Sum 20
	*/
	//   Test Cases
	$tree1->find_subtree();
	/*
	  		    Second Tree Result 
	  		    -----------------   
	  		         10                            
	  		       /   \    
	  		      3     3     
	  		     /     /  \               
	  		    8     7    8
	  		------------------
	  		Sum 39
	*/
	$tree2->find_subtree();
	/*
	  		    Third Tree Result 
	  		    -------------------                          
	  		          3       
	  		         /                   
	  		        1
	  		         \        
	  		          6  
	  		 -----------------
	  		Sum 10
	*/
	$tree3->find_subtree();
}
main();

Output

 Tree Elements
  6  -15  1  3  10  8  -1  7  -8
 Max Sum Subtree : 20

 Tree Elements
  10  3  8  3  7  8
 Max Sum Subtree : 39

 Tree Elements
  20  3  1  6  3  1  -36
 Max Sum Subtree : 10
/*
     Node Js Program 
     Find largest subtree sum in a tree
*/

//  Binary Tree node
class Node
{
	constructor(data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		// Set initial tree root to null
		this.root = null;
		this.result = 0;
	}
	// Display pre order elements
	preorder(node)
	{
		if (node != null)
		{
			// Print node value
			process.stdout.write("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	//  Returns the max value of two numbers
	max_value(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	//  Returns the largest sum of subtree
	largest_sum_subtree(node)
	{
		if (node != null)
		{
			// return the result of current subtree
			//  Recursively, Find the sum of subtree
			var sum = node.data + this.largest_sum_subtree(node.left) + this.largest_sum_subtree(node.right);
			//  Get the max sum of previous and current subtree
			this.result = this.max_value(sum, this.result);
			return sum;
		}
		else
		{
			return 0;
		}
	}
	// Handles the request to find largest subtree of max sum
	find_subtree()
	{
		if (this.root != null)
		{
			process.stdout.write("\n Tree Elements \n");
			// Display tree elements
			this.preorder(this.root);
			this.result = -Number.MAX_VALUE;
			this.largest_sum_subtree(this.root);
			//  Display calculated result
			process.stdout.write("\n Max Sum Subtree : " + this.result + "\n");
		}
		else
		{
			process.stdout.write("\n Empty Tree \n");
		}
	}
}

function main()
{
	// Create tree objects
	var tree1 = new BinaryTree();
	var tree2 = new BinaryTree();
	var tree3 = new BinaryTree();
	/*
	  		    constructor binary tree
	  		    -----------------
	  		         6                            
	  		       /   \    
	  		     -15    7    
	  		     / \     \               
	  		    1   3     -8  
	  		       / \
	  		      10  8
	  		           \
	  		           -1
	  		-----------------
	  		First Tree
	*/
	tree1.root = new Node(6);
	tree1.root.left = new Node(-15);
	tree1.root.left.right = new Node(3);
	tree1.root.left.right.left = new Node(10);
	tree1.root.left.right.right = new Node(8);
	tree1.root.left.right.right.right = new Node(-1);
	tree1.root.left.left = new Node(1);
	tree1.root.right = new Node(7);
	tree1.root.right.right = new Node(-8);
	/*
	  		    constructor binary tree
	  		    -----------------
	  		        10                            
	  		       /   \    
	  		      3     3     
	  		     /     /  \               
	  		    8     7    8
	  		   -----------------
	  		   Second Tree
	*/
	tree2.root = new Node(10);
	tree2.root.right = new Node(3);
	tree2.root.right.right = new Node(8);
	tree2.root.right.left = new Node(7);
	tree2.root.left = new Node(3);
	tree2.root.left.left = new Node(8);
	/*
	  		    constructor binary tree
	  		    -----------------
	  		        20                            
	  		       /   \    
	  		      3     3     
	  		     /        \               
	  		    1          1
	  		     \        /
	  		      6     -36  
	  		    -----------------
	  		    Third Tree
	*/
	tree3.root = new Node(20);
	tree3.root.right = new Node(3);
	tree3.root.right.right = new Node(1);
	tree3.root.right.right.left = new Node(-36);
	tree3.root.left = new Node(3);
	tree3.root.left.left = new Node(1);
	tree3.root.left.left.right = new Node(6);
	/*
	  		    First Tree Result 
	  		    -----------------
	  		        3  
	  		       / \
	  		      10  8
	  		           \
	  		            -1
	  		 ----------------
	  		 Sum 20
	*/
	//   Test Cases
	tree1.find_subtree();
	/*
	  		    Second Tree Result 
	  		    -----------------   
	  		         10                            
	  		       /   \    
	  		      3     3     
	  		     /     /  \               
	  		    8     7    8
	  		------------------
	  		Sum 39
	*/
	tree2.find_subtree();
	/*
	  		    Third Tree Result 
	  		    -------------------                          
	  		          3       
	  		         /                   
	  		        1
	  		         \        
	  		          6  
	  		 -----------------
	  		Sum 10
	*/
	tree3.find_subtree();
}
main();

Output

 Tree Elements
  6  -15  1  3  10  8  -1  7  -8
 Max Sum Subtree : 20

 Tree Elements
  10  3  8  3  7  8
 Max Sum Subtree : 39

 Tree Elements
  20  3  1  6  3  1  -36
 Max Sum Subtree : 10
import sys
# 
#     Python 3 Program 
#     Find largest subtree sum in a tree

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

class BinaryTree :
	
	def __init__(self) :
		# Set initial tree root to null
		self.root = None
		self.result = 0
	
	# Display pre order elements
	def preorder(self, node) :
		if (node != None) :
			# Print node value
			print("  ", node.data, end = "")
			self.preorder(node.left)
			self.preorder(node.right)
		
	
	#  Returns the max value of two numbers
	def max_value(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	#  Returns the largest sum of subtree
	def largest_sum_subtree(self, node) :
		if (node != None) :
			#  Recursively, Find the sum of subtree
			sum = node.data + self.largest_sum_subtree(node.left) + self.largest_sum_subtree(node.right)
			#  Get the max sum of previous and current subtree
			self.result = self.max_value(sum, self.result)
			# return the result of current subtree
			return sum
		else :
			return 0
		
	
	# Handles the request to find largest subtree of max sum
	def find_subtree(self) :
		if (self.root != None) :
			print("\n Tree Elements \n", end = "")
			# Display tree elements
			self.preorder(self.root)
			self.result = -sys.maxsize
			self.largest_sum_subtree(self.root)
			#  Display calculated result
			print("\n Max Sum Subtree : ", self.result ,"\n", end = "")
		else :
			print("\n Empty Tree \n", end = "")
		
	

def main() :
	# Create tree objects
	tree1 = BinaryTree()
	tree2 = BinaryTree()
	tree3 = BinaryTree()
	# 
	# 		    constructor binary tree
	# 		    -----------------
	# 		         6                            
	# 		       /   \    
	# 		     -15    7    
	# 		     / \     \               
	# 		    1   3     -8  
	# 		       / \
	# 		      10  8
	# 		           \
	# 		           -1
	# 		-----------------
	# 		First Tree
	# 		
	
	tree1.root = Node(6)
	tree1.root.left = Node(-15)
	tree1.root.left.right = Node(3)
	tree1.root.left.right.left = Node(10)
	tree1.root.left.right.right = Node(8)
	tree1.root.left.right.right.right = Node(-1)
	tree1.root.left.left = Node(1)
	tree1.root.right = Node(7)
	tree1.root.right.right = Node(-8)
	# 
	# 		    constructor binary tree
	# 		    -----------------
	# 		        10                            
	# 		       /   \    
	# 		      3     3     
	# 		     /     /  \               
	# 		    8     7    8
	# 		           
	# 		   -----------------
	# 		   Second Tree
	# 		
	
	tree2.root = Node(10)
	tree2.root.right = Node(3)
	tree2.root.right.right = Node(8)
	tree2.root.right.left = Node(7)
	tree2.root.left = Node(3)
	tree2.root.left.left = Node(8)
	# 
	# 		    constructor binary tree
	# 		    -----------------
	# 		        20                            
	# 		       /   \    
	# 		      3     3     
	# 		     /        \               
	# 		    1          1
	# 		     \        /
	# 		      6     -36  
	# 		            
	# 		    -----------------
	# 		    Third Tree
	# 		    
	
	tree3.root = Node(20)
	tree3.root.right = Node(3)
	tree3.root.right.right = Node(1)
	tree3.root.right.right.left = Node(-36)
	tree3.root.left = Node(3)
	tree3.root.left.left = Node(1)
	tree3.root.left.left.right = Node(6)
	# 
	# 		    First Tree Result 
	# 		    -----------------
	# 		        3  
	# 		       / \
	# 		      10  8
	# 		           \
	# 		            -1
	# 		 ----------------
	# 		 Sum 20
	# 		 
	
	#   Test Cases
	tree1.find_subtree()
	# 
	# 		    Second Tree Result 
	# 		    -----------------   
	# 		         10                            
	# 		       /   \    
	# 		      3     3     
	# 		     /     /  \               
	# 		    8     7    8
	# 		------------------
	# 		Sum 39
	# 		
	
	tree2.find_subtree()
	# 
	# 		    Third Tree Result 
	# 		    -------------------                          
	# 		          3       
	# 		         /                   
	# 		        1
	# 		         \        
	# 		          6  
	# 		            
	# 		 -----------------
	# 		Sum 10
	# 		
	
	tree3.find_subtree()

if __name__ == "__main__": main()

Output

 Tree Elements
   6   -15   1   3   10   8   -1   7   -8
 Max Sum Subtree :  20

 Tree Elements
   10   3   8   3   7   8
 Max Sum Subtree :  39

 Tree Elements
   20   3   1   6   3   1   -36
 Max Sum Subtree :  10
#     Ruby Program 
#     Find largest subtree sum in a tree

#  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 BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root, :result
	attr_accessor :root, :result
 
	
	def initialize() 
		# Set initial tree root to null
		self.root = nil
		self.result = 0
	end

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

	end

	#  Returns the max value of two numbers
	def max_value(a, b) 
		if (a > b) 
			return a
		else 
			return b
		end

	end

	#  Returns the largest sum of subtree
	def largest_sum_subtree(node) 
		if (node != nil) 
			#  Recursively, Find the sum of subtree
			sum = node.data + self.largest_sum_subtree(node.left) + self.largest_sum_subtree(node.right)
			#  Get the max sum of previous and current subtree
			self.result = self.max_value(sum, self.result)
			# return the result of current subtree
			return sum
		else 
			return 0
		end

	end

	# Handles the request to find largest subtree of max sum
	def find_subtree() 
		if (self.root != nil) 
			print("\n Tree Elements \n")
			# Display tree elements
			self.preorder(self.root)
			self.result = -(2 ** (0. size * 8 - 2))
			self.largest_sum_subtree(self.root)
			#  Display calculated result
			print("\n Max Sum Subtree : ", self.result ,"\n")
		else 
			print("\n Empty Tree \n")
		end

	end

end

def main() 
	# Create tree objects
	tree1 = BinaryTree.new()
	tree2 = BinaryTree.new()
	tree3 = BinaryTree.new()
	# 
	# 		    constructor binary tree
	# 		    -----------------
	# 		         6                            
	# 		       /   \    
	# 		     -15    7    
	# 		     / \     \               
	# 		    1   3     -8  
	# 		       / \
	# 		      10  8
	# 		           \
	# 		           -1
	# 		-----------------
	# 		First Tree
	# 		
	
	tree1.root = Node.new(6)
	tree1.root.left = Node.new(-15)
	tree1.root.left.right = Node.new(3)
	tree1.root.left.right.left = Node.new(10)
	tree1.root.left.right.right = Node.new(8)
	tree1.root.left.right.right.right = Node.new(-1)
	tree1.root.left.left = Node.new(1)
	tree1.root.right = Node.new(7)
	tree1.root.right.right = Node.new(-8)
	# 
	# 		    constructor binary tree
	# 		    -----------------
	# 		        10                            
	# 		       /   \    
	# 		      3     3     
	# 		     /     /  \               
	# 		    8     7    8
	# 		           
	# 		   -----------------
	# 		   Second Tree
	# 		
	
	tree2.root = Node.new(10)
	tree2.root.right = Node.new(3)
	tree2.root.right.right = Node.new(8)
	tree2.root.right.left = Node.new(7)
	tree2.root.left = Node.new(3)
	tree2.root.left.left = Node.new(8)
	# 
	# 		    constructor binary tree
	# 		    -----------------
	# 		        20                            
	# 		       /   \    
	# 		      3     3     
	# 		     /        \               
	# 		    1          1
	# 		     \        /
	# 		      6     -36  
	# 		            
	# 		    -----------------
	# 		    Third Tree
	# 		    
	
	tree3.root = Node.new(20)
	tree3.root.right = Node.new(3)
	tree3.root.right.right = Node.new(1)
	tree3.root.right.right.left = Node.new(-36)
	tree3.root.left = Node.new(3)
	tree3.root.left.left = Node.new(1)
	tree3.root.left.left.right = Node.new(6)
	# 
	# 		    First Tree Result 
	# 		    -----------------
	# 		        3  
	# 		       / \
	# 		      10  8
	# 		           \
	# 		            -1
	# 		 ----------------
	# 		 Sum 20
	# 		 
	
	#   Test Cases
	tree1.find_subtree()
	# 
	# 		    Second Tree Result 
	# 		    -----------------   
	# 		         10                            
	# 		       /   \    
	# 		      3     3     
	# 		     /     /  \               
	# 		    8     7    8
	# 		------------------
	# 		Sum 39
	# 		
	
	tree2.find_subtree()
	# 
	# 		    Third Tree Result 
	# 		    -------------------                          
	# 		          3       
	# 		         /                   
	# 		        1
	# 		         \        
	# 		          6  
	# 		            
	# 		 -----------------
	# 		Sum 10
	# 		
	
	tree3.find_subtree()
end

main()

Output

 Tree Elements 
  6  -15  1  3  10  8  -1  7  -8
 Max Sum Subtree : 20

 Tree Elements 
  10  3  8  3  7  8
 Max Sum Subtree : 39

 Tree Elements 
  20  3  1  6  3  1  -36
 Max Sum Subtree : 10
/*
     Scala Program 
     Find largest subtree sum in a tree
*/

//  Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinaryTree(var root: Node , var result: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Display pre order elements
	def preorder(node: Node): Unit = {
		if (node != null)
		{
			// Print node value
			print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//  Returns the max value of two numbers
	def max_value(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	//  Returns the largest sum of subtree
	def largest_sum_subtree(node: Node): Int = {
		if (node != null)
		{
			// return the result of current subtree
			//  Recursively, Find the sum of subtree
			var sum: Int = node.data + largest_sum_subtree(node.left) + largest_sum_subtree(node.right);
			//  Get the max sum of previous and current subtree
			this.result = max_value(sum, this.result);
			return sum;
		}
		else
		{
			return 0;
		}
	}
	// Handles the request to find largest subtree of max sum
	def find_subtree(): Unit = {
		if (this.root != null)
		{
			print("\n Tree Elements \n");
			// Display tree elements
			preorder(this.root);
			this.result = Int.MinValue;
			largest_sum_subtree(this.root);
			//  Display calculated result
			print("\n Max Sum Subtree : " + this.result + "\n");
		}
		else
		{
			print("\n Empty Tree \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create tree objects
		var tree1: BinaryTree = new BinaryTree();
		var tree2: BinaryTree = new BinaryTree();
		var tree3: BinaryTree = new BinaryTree();
		/*
		  		    constructor binary tree
		  		    -----------------
		  		         6                            
		  		       /   \    
		  		     -15    7    
		  		     / \     \               
		  		    1   3     -8  
		  		       / \
		  		      10  8
		  		           \
		  		           -1
		  		-----------------
		  		First Tree
		*/
		tree1.root = new Node(6);
		tree1.root.left = new Node(-15);
		tree1.root.left.right = new Node(3);
		tree1.root.left.right.left = new Node(10);
		tree1.root.left.right.right = new Node(8);
		tree1.root.left.right.right.right = new Node(-1);
		tree1.root.left.left = new Node(1);
		tree1.root.right = new Node(7);
		tree1.root.right.right = new Node(-8);
		/*
		  		    constructor binary tree
		  		    -----------------
		  		        10                            
		  		       /   \    
		  		      3     3     
		  		     /     /  \               
		  		    8     7    8
		  		   -----------------
		  		   Second Tree
		*/
		tree2.root = new Node(10);
		tree2.root.right = new Node(3);
		tree2.root.right.right = new Node(8);
		tree2.root.right.left = new Node(7);
		tree2.root.left = new Node(3);
		tree2.root.left.left = new Node(8);
		/*
		  		    constructor binary tree
		  		    -----------------
		  		        20                            
		  		       /   \    
		  		      3     3     
		  		     /        \               
		  		    1          1
		  		     \        /
		  		      6     -36  
		  		    -----------------
		  		    Third Tree
		*/
		tree3.root = new Node(20);
		tree3.root.right = new Node(3);
		tree3.root.right.right = new Node(1);
		tree3.root.right.right.left = new Node(-36);
		tree3.root.left = new Node(3);
		tree3.root.left.left = new Node(1);
		tree3.root.left.left.right = new Node(6);
		/*
		  		    First Tree Result 
		  		    -----------------
		  		        3  
		  		       / \
		  		      10  8
		  		           \
		  		            -1
		  		 ----------------
		  		 Sum 20
		*/
		//   Test Cases
		tree1.find_subtree();
		/*
		  		    Second Tree Result 
		  		    -----------------   
		  		         10                            
		  		       /   \    
		  		      3     3     
		  		     /     /  \               
		  		    8     7    8
		  		------------------
		  		Sum 39
		*/
		tree2.find_subtree();
		/*
		  		    Third Tree Result 
		  		    -------------------                          
		  		          3       
		  		         /                   
		  		        1
		  		         \        
		  		          6  
		  		 -----------------
		  		Sum 10
		*/
		tree3.find_subtree();
	}
}

Output

 Tree Elements
  6  -15  1  3  10  8  -1  7  -8
 Max Sum Subtree : 20

 Tree Elements
  10  3  8  3  7  8
 Max Sum Subtree : 39

 Tree Elements
  20  3  1  6  3  1  -36
 Max Sum Subtree : 10
/*
     Swift 4 Program 
     Find largest subtree sum in a tree
*/
//  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 BinaryTree
{
	var root: Node? ;
	var result: Int;
	init()
	{
		// Set initial tree root to null
		self.root = nil;
		self.result = 0;
	}
	// Display pre order elements
	func preorder(_ node: Node? )
	{
		if (node != nil)
		{
			// Print node value
			print("  ", node!.data, terminator: "");
			self.preorder(node!.left);
			self.preorder(node!.right);
		}
	}
	//  Returns the max value of two numbers
	func max_value(_ a: Int, _ b: Int)->Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	//  Returns the largest sum of subtree
	func largest_sum_subtree(_ node: Node? )->Int
	{
		if (node != nil)
		{
			// return the result of current subtree
			//  Recursively, Find the sum of subtree
			let sum: Int = node!.data + self.largest_sum_subtree(node!.left) + self.largest_sum_subtree(node!.right);
			//  Get the max sum of previous and current subtree
			self.result = self.max_value(sum, self.result);
			return sum;
		}
		else
		{
			return 0;
		}
	}
	// Handles the request to find largest subtree of max sum
	func find_subtree()
	{
		if (self.root != nil)
		{
			print("\n Tree Elements ");
			// Display tree elements
			self.preorder(self.root);
			self.result = Int.min;
			let _ = self.largest_sum_subtree(self.root);
			//  Display calculated result
			print("\n Max Sum Subtree : ", self.result );
		}
		else
		{
			print("\n Empty Tree \n", terminator: "");
		}
	}
}
func main()
{
	// Create tree objects
	let tree1: BinaryTree = BinaryTree();
	let tree2: BinaryTree = BinaryTree();
	let tree3: BinaryTree = BinaryTree();
	/*
  		    constructor binary tree
  		    -----------------
  		         6                            
  		       /   \    
  		     -15    7    
  		     / \     \               
  		    1   3     -8  
  		       / \
  		      10  8
  		           \
  		           -1
  		-----------------
  		First Tree
*/
	tree1.root = Node(6);
	tree1.root!.left = Node(-15);
	tree1.root!.left!.right = Node(3);
	tree1.root!.left!.right!.left = Node(10);
	tree1.root!.left!.right!.right = Node(8);
	tree1.root!.left!.right!.right!.right = Node(-1);
	tree1.root!.left!.left = Node(1);
	tree1.root!.right = Node(7);
	tree1.root!.right!.right = Node(-8);
	/*
  		    constructor binary tree
  		    -----------------
  		        10                            
  		       /   \    
  		      3     3     
  		     /     /  \               
  		    8     7    8
  		   -----------------
  		   Second Tree
*/
	tree2.root = Node(10);
	tree2.root!.right = Node(3);
	tree2.root!.right!.right = Node(8);
	tree2.root!.right!.left = Node(7);
	tree2.root!.left = Node(3);
	tree2.root!.left!.left = Node(8);
	/*
  		    constructor binary tree
  		    -----------------
  		        20                            
  		       /   \    
  		      3     3     
  		     /        \               
  		    1          1
  		     \        /
  		      6     -36  
  		    -----------------
  		    Third Tree
*/
	tree3.root = Node(20);
	tree3.root!.right = Node(3);
	tree3.root!.right!.right = Node(1);
	tree3.root!.right!.right!.left = Node(-36);
	tree3.root!.left = Node(3);
	tree3.root!.left!.left = Node(1);
	tree3.root!.left!.left!.right = Node(6);
	/*
  		    First Tree Result 
  		    -----------------
  		        3  
  		       / \
  		      10  8
  		           \
  		            -1
  		 ----------------
  		 Sum 20
*/
	//   Test Cases
	tree1.find_subtree();
	/*
  		    Second Tree Result 
  		    -----------------   
  		         10                            
  		       /   \    
  		      3     3     
  		     /     /  \               
  		    8     7    8
  		------------------
  		Sum 39
*/
	tree2.find_subtree();
	/*
  		    Third Tree Result 
  		    -------------------                          
  		          3       
  		         /                   
  		        1
  		         \        
  		          6  
  		 -----------------
  		Sum 10
*/
	tree3.find_subtree();
}
main();

Output

 Tree Elements
   6   -15   1   3   10   8   -1   7   -8
 Max Sum Subtree :  20

 Tree Elements
   10   3   8   3   7   8
 Max Sum Subtree :  39

 Tree Elements
   20   3   1   6   3   1   -36
 Max Sum Subtree :  10

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