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 : 10import 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
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