Print all subtrees of given sum in binary tree
Here given code implementation process.
/*
C Program
Print all subtrees of given sum in binary tree
*/
#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 inorder elements
void print_subtree(struct Node *node)
{
if (node != NULL)
{
print_subtree(node->left);
//Print node value
printf(" %d", node->data);
print_subtree(node->right);
}
}
//Find subtree of given sum
int subtree_sum(struct Node *node, int sum)
{
if (node == NULL)
{
return 0;
}
// calculate the sum of left and right subtree and current node
int k = subtree_sum(node->left, sum) + subtree_sum(node->right, sum) + node->data;
if (k == sum)
{
//When sum exist
printf("\n");
print_subtree(node);
}
return k;
}
// Handles the request to find subtree of given sum
void subtree(struct Node *root, int sum)
{
if (root == NULL)
{
printf("\n Empty Tree \n");
}
else
{
printf("\n Subtree of sum %d are ", sum);
subtree_sum(root, sum);
printf("\n");
}
}
int main()
{
struct Node *root = NULL;
/* Binary Tree
-----------------------
5
/ \
3 -2
/ \ / \
2 2 2 10
/ / \ / \
1 -4 2 1 -5
*/
//Add nodes
root = get_node(5);
root->left = get_node(3);
root->right = get_node(-2);
root->right->right = get_node(10);
root->right->right->left = get_node(1);
root->right->right->right = get_node(-5);
root->right->left = get_node(2);
root->left->left = get_node(2);
root->left->left->left = get_node(1);
root->left->right = get_node(2);
root->left->right->left = get_node(-4);
root->left->right->right = get_node(2);
int sum = 6;
subtree(root, sum);
return 0;
}
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
/*
Java Program
Print all subtrees of given sum in binary 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;
}
}
//Define Binary Tree
public class BinaryTree
{
public Node root;
public BinaryTree()
{
//Set root of tree
this.root = null;
}
//Display inorder elements
public void print_subtree(Node node)
{
if (node != null)
{
print_subtree(node.left);
//Print node value
System.out.print(" " + node.data);
print_subtree(node.right);
}
}
// Print all subtrees with given sum in a Binary Tree
public int subtree_sum(Node node, int sum)
{
if (node == null)
{
return 0;
}
// calculate the sum of left and right subtree and current node
int k = subtree_sum(node.left, sum) + subtree_sum(node.right, sum) + node.data;
if (k == sum)
{
//When sum exist
System.out.print("\n");
print_subtree(node);
}
return k;
}
// Handles the request to find subtree of given sum
public void subtree(int sum)
{
if (this.root == null)
{
System.out.print("\n Empty Tree \n");
}
else
{
System.out.print("\n Subtree of sum " + sum + " are ");
subtree_sum(this.root, sum);
System.out.print("\n");
}
}
public static void main(String[] args)
{
//Create tree object
BinaryTree tree = new BinaryTree();
/* Binary Tree
-----------------------
5
/ \
3 -2
/ \ / \
2 2 2 10
/ / \ / \
1 -4 2 1 -5
*/
//Add nodes
tree.root = new Node(5);
tree.root.left = new Node(3);
tree.root.right = new Node(-2);
tree.root.right.right = new Node(10);
tree.root.right.right.left = new Node(1);
tree.root.right.right.right = new Node(-5);
tree.root.right.left = new Node(2);
tree.root.left.left = new Node(2);
tree.root.left.left.left = new Node(1);
tree.root.left.right = new Node(2);
tree.root.left.right.left = new Node(-4);
tree.root.left.right.right = new Node(2);
int sum = 6;
tree.subtree(sum);
}
}
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Print all subtrees of given sum in binary 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;
}
};
// Define Binary Tree
class BinaryTree
{
public: Node *root;
BinaryTree()
{
// Set root of tree
this->root = NULL;
}
// Display inorder elements
void print_subtree(Node *node)
{
if (node != NULL)
{
this->print_subtree(node->left);
// Print node value
cout << " " << node->data;
this->print_subtree(node->right);
}
}
// Print all subtrees with given sum in a Binary Tree
int subtree_sum(Node *node, int sum)
{
if (node == NULL)
{
return 0;
}
// calculate the sum of left and right subtree and current node
int k = this->subtree_sum(node->left, sum) + this->subtree_sum(node->right, sum) + node->data;
if (k == sum)
{
// When sum exist
cout << "\n";
this->print_subtree(node);
}
return k;
}
// Handles the request to find subtree of given sum
void subtree(int sum)
{
if (this->root == NULL)
{
cout << "\n Empty Tree \n";
}
else
{
cout << "\n Subtree of sum " << sum << " are ";
this->subtree_sum(this->root, sum);
cout << "\n";
}
}
};
int main()
{
// Create tree object
BinaryTree tree = BinaryTree();
// Binary Tree
// -----------------------
// 5
// / \
// 3 -2
// / \ / \
// 2 2 2 10
// / / \ / \
// 1 -4 2 1 -5
//
//
// Add nodes
tree.root = new Node(5);
tree.root->left = new Node(3);
tree.root->right = new Node(-2);
tree.root->right->right = new Node(10);
tree.root->right->right->left = new Node(1);
tree.root->right->right->right = new Node(-5);
tree.root->right->left = new Node(2);
tree.root->left->left = new Node(2);
tree.root->left->left->left = new Node(1);
tree.root->left->right = new Node(2);
tree.root->left->right->left = new Node(-4);
tree.root->left->right->right = new Node(2);
int sum = 6;
tree.subtree(sum);
return 0;
}
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
// Include namespace system
using System;
// C# Program
// Print all subtrees of given sum in binary 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;
}
}
// Define Binary Tree
public class BinaryTree
{
public Node root;
public BinaryTree()
{
// Set root of tree
this.root = null;
}
// Display inorder elements
public void print_subtree(Node node)
{
if (node != null)
{
print_subtree(node.left);
// Print node value
Console.Write(" " + node.data);
print_subtree(node.right);
}
}
// Print all subtrees with given sum in a Binary Tree
public int subtree_sum(Node node, int sum)
{
if (node == null)
{
return 0;
}
// calculate the sum of left and right subtree and current node
int k = subtree_sum(node.left, sum) + subtree_sum(node.right, sum) + node.data;
if (k == sum)
{
// When sum exist
Console.Write("\n");
print_subtree(node);
}
return k;
}
// Handles the request to find subtree of given sum
public void subtree(int sum)
{
if (this.root == null)
{
Console.Write("\n Empty Tree \n");
}
else
{
Console.Write("\n Subtree of sum " + sum + " are ");
subtree_sum(this.root, sum);
Console.Write("\n");
}
}
public static void Main(String[] args)
{
// Create tree object
BinaryTree tree = new BinaryTree();
// Binary Tree
// -----------------------
// 5
// / \
// 3 -2
// / \ / \
// 2 2 2 10
// / / \ / \
// 1 -4 2 1 -5
//
//
// Add nodes
tree.root = new Node(5);
tree.root.left = new Node(3);
tree.root.right = new Node(-2);
tree.root.right.right = new Node(10);
tree.root.right.right.left = new Node(1);
tree.root.right.right.right = new Node(-5);
tree.root.right.left = new Node(2);
tree.root.left.left = new Node(2);
tree.root.left.left.left = new Node(1);
tree.root.left.right = new Node(2);
tree.root.left.right.left = new Node(-4);
tree.root.left.right.right = new Node(2);
int sum = 6;
tree.subtree(sum);
}
}
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
<?php
// Php Program
// Print all subtrees of given sum in binary 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;
}
}
// Define Binary Tree
class BinaryTree
{
public $root;
function __construct()
{
// Set root of tree
$this->root = null;
}
// Display inorder elements
public function print_subtree($node)
{
if ($node != null)
{
$this->print_subtree($node->left);
// Print node value
echo " ". $node->data;
$this->print_subtree($node->right);
}
}
// Print all subtrees with given sum in a Binary Tree
public function subtree_sum($node, $sum)
{
if ($node == null)
{
return 0;
}
// calculate the sum of left and right subtree and current node
$k = $this->subtree_sum($node->left, $sum) + $this->subtree_sum($node->right, $sum) + $node->data;
if ($k == $sum)
{
// When sum exist
echo "\n";
$this->print_subtree($node);
}
return $k;
}
// Handles the request to find subtree of given sum
public function subtree($sum)
{
if ($this->root == null)
{
echo "\n Empty Tree \n";
}
else
{
echo "\n Subtree of sum ". $sum ." are ";
$this->subtree_sum($this->root, $sum);
echo "\n";
}
}
}
function main()
{
// Create tree object
$tree = new BinaryTree();
// Binary Tree
// -----------------------
// 5
// / \
// 3 -2
// / \ / \
// 2 2 2 10
// / / \ / \
// 1 -4 2 1 -5
//
//
// Add nodes
$tree->root = new Node(5);
$tree->root->left = new Node(3);
$tree->root->right = new Node(-2);
$tree->root->right->right = new Node(10);
$tree->root->right->right->left = new Node(1);
$tree->root->right->right->right = new Node(-5);
$tree->root->right->left = new Node(2);
$tree->root->left->left = new Node(2);
$tree->root->left->left->left = new Node(1);
$tree->root->left->right = new Node(2);
$tree->root->left->right->left = new Node(-4);
$tree->root->left->right->right = new Node(2);
$sum = 6;
$tree->subtree($sum);
}
main();
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
// Node Js Program
// Print all subtrees of given sum in binary tree
// Binary Tree node
class Node
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
// Set root of tree
this.root = null;
}
// Display inorder elements
print_subtree(node)
{
if (node != null)
{
this.print_subtree(node.left);
// Print node value
process.stdout.write(" " + node.data);
this.print_subtree(node.right);
}
}
// Print all subtrees with given sum in a Binary Tree
subtree_sum(node, sum)
{
if (node == null)
{
return 0;
}
// calculate the sum of left and right subtree and current node
var k = this.subtree_sum(node.left, sum) + this.subtree_sum(node.right, sum) + node.data;
if (k == sum)
{
// When sum exist
process.stdout.write("\n");
this.print_subtree(node);
}
return k;
}
// Handles the request to find subtree of given sum
subtree(sum)
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree \n");
}
else
{
process.stdout.write("\n Subtree of sum " + sum + " are ");
this.subtree_sum(this.root, sum);
process.stdout.write("\n");
}
}
}
function main()
{
// Create tree object
var tree = new BinaryTree();
// Binary Tree
// -----------------------
// 5
// / \
// 3 -2
// / \ / \
// 2 2 2 10
// / / \ / \
// 1 -4 2 1 -5
//
//
// Add nodes
tree.root = new Node(5);
tree.root.left = new Node(3);
tree.root.right = new Node(-2);
tree.root.right.right = new Node(10);
tree.root.right.right.left = new Node(1);
tree.root.right.right.right = new Node(-5);
tree.root.right.left = new Node(2);
tree.root.left.left = new Node(2);
tree.root.left.left.left = new Node(1);
tree.root.left.right = new Node(2);
tree.root.left.right.left = new Node(-4);
tree.root.left.right.right = new Node(2);
var sum = 6;
tree.subtree(sum);
}
main();
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
# Python 3 Program
# Print all subtrees of given sum in binary tree
# Binary Tree node
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
# Define Binary Tree
class BinaryTree :
def __init__(self) :
# Set root of tree
self.root = None
# Display inorder elements
def print_subtree(self, node) :
if (node != None) :
self.print_subtree(node.left)
# Print node value
print(" ", node.data, end = "")
self.print_subtree(node.right)
# Print all subtrees with given sum in a Binary Tree
def subtree_sum(self, node, sum) :
if (node == None) :
return 0
# calculate the sum of left and right subtree and current node
k = self.subtree_sum(node.left, sum) + self.subtree_sum(node.right, sum) + node.data
if (k == sum) :
# When sum exist
print("\n", end = "")
self.print_subtree(node)
return k
# Handles the request to find subtree of given sum
def subtree(self, sum) :
if (self.root == None) :
print("\n Empty Tree \n", end = "")
else :
print("\n Subtree of sum ", sum ," are ", end = "")
self.subtree_sum(self.root, sum)
print("\n", end = "")
def main() :
# Create tree object
tree = BinaryTree()
# Binary Tree
# -----------------------
# 5
# / \
# 3 -2
# / \ / \
# 2 2 2 10
# / / \ / \
# 1 -4 2 1 -5
#
#
# Add nodes
tree.root = Node(5)
tree.root.left = Node(3)
tree.root.right = Node(-2)
tree.root.right.right = Node(10)
tree.root.right.right.left = Node(1)
tree.root.right.right.right = Node(-5)
tree.root.right.left = Node(2)
tree.root.left.left = Node(2)
tree.root.left.left.left = Node(1)
tree.root.left.right = Node(2)
tree.root.left.right.left = Node(-4)
tree.root.left.right.right = Node(2)
sum = 6
tree.subtree(sum)
if __name__ == "__main__": main()
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
# Ruby Program
# Print all subtrees of given sum in binary 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
# 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 inorder elements
def print_subtree(node)
if (node != nil)
self.print_subtree(node.left)
# Print node value
print(" ", node.data)
self.print_subtree(node.right)
end
end
# Print all subtrees with given sum in a Binary Tree
def subtree_sum(node, sum)
if (node == nil)
return 0
end
# calculate the sum of left and right subtree and current node
k = self.subtree_sum(node.left, sum) + self.subtree_sum(node.right, sum) + node.data
if (k == sum)
# When sum exist
print("\n")
self.print_subtree(node)
end
return k
end
# Handles the request to find subtree of given sum
def subtree(sum)
if (self.root == nil)
print("\n Empty Tree \n")
else
print("\n Subtree of sum ", sum ," are ")
self.subtree_sum(self.root, sum)
print("\n")
end
end
end
def main()
# Create tree object
tree = BinaryTree.new()
# Binary Tree
# -----------------------
# 5
# / \
# 3 -2
# / \ / \
# 2 2 2 10
# / / \ / \
# 1 -4 2 1 -5
#
#
# Add nodes
tree.root = Node.new(5)
tree.root.left = Node.new(3)
tree.root.right = Node.new(-2)
tree.root.right.right = Node.new(10)
tree.root.right.right.left = Node.new(1)
tree.root.right.right.right = Node.new(-5)
tree.root.right.left = Node.new(2)
tree.root.left.left = Node.new(2)
tree.root.left.left.left = Node.new(1)
tree.root.left.right = Node.new(2)
tree.root.left.right.left = Node.new(-4)
tree.root.left.right.right = Node.new(2)
sum = 6
tree.subtree(sum)
end
main()
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
// Scala Program
// Print all subtrees of given sum in binary tree
// Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Define Binary Tree
class BinaryTree(var root: Node)
{
def this()
{
this(null);
}
// Display inorder elements
def print_subtree(node: Node): Unit = {
if (node != null)
{
print_subtree(node.left);
// Print node value
print(" " + node.data);
print_subtree(node.right);
}
}
// Print all subtrees with given sum in a Binary Tree
def subtree_sum(node: Node, sum: Int): Int = {
if (node == null)
{
return 0;
}
// calculate the sum of left and right subtree and current node
var k: Int = subtree_sum(node.left, sum) + subtree_sum(node.right, sum) + node.data;
if (k == sum)
{
// When sum exist
print("\n");
print_subtree(node);
}
return k;
}
// Handles the request to find subtree of given sum
def subtree(sum: Int): Unit = {
if (this.root == null)
{
print("\n Empty Tree \n");
}
else
{
print("\n Subtree of sum " + sum + " are ");
subtree_sum(this.root, sum);
print("\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create tree object
var tree: BinaryTree = new BinaryTree();
// Binary Tree
// -----------------------
// 5
// / \
// 3 -2
// / \ / \
// 2 2 2 10
// / / \ / \
// 1 -4 2 1 -5
//
//
// Add nodes
tree.root = new Node(5);
tree.root.left = new Node(3);
tree.root.right = new Node(-2);
tree.root.right.right = new Node(10);
tree.root.right.right.left = new Node(1);
tree.root.right.right.right = new Node(-5);
tree.root.right.left = new Node(2);
tree.root.left.left = new Node(2);
tree.root.left.left.left = new Node(1);
tree.root.left.right = new Node(2);
tree.root.left.right.left = new Node(-4);
tree.root.left.right.right = new Node(2);
var sum: Int = 6;
tree.subtree(sum);
}
}
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
// Swift 4 Program
// Print all subtrees of given sum in binary 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;
}
}
// Define Binary Tree
class BinaryTree
{
var root: Node? ;
init()
{
// Set root of tree
self.root = nil;
}
// Display inorder elements
func print_subtree(_ node: Node? )
{
if (node != nil)
{
self.print_subtree(node!.left);
// Print node value
print(" ", node!.data, terminator: "");
self.print_subtree(node!.right);
}
}
// Print all subtrees with given sum in a Binary Tree
func subtree_sum(_ node: Node? , _ sum : Int)->Int
{
if (node == nil)
{
return 0;
}
// calculate the sum of left and right subtree and current node
let k: Int = self.subtree_sum(node!.left, sum) + self.subtree_sum(node!.right, sum) + node!.data;
if (k == sum)
{
// When sum exist
print("\n", terminator: "");
self.print_subtree(node);
}
return k;
}
// Handles the request to find subtree of given sum
func subtree(_ sum: Int)
{
if (self.root == nil)
{
print("\n Empty Tree \n", terminator: "");
}
else
{
print("\n Subtree of sum ", sum ," are ", terminator: "");
let _ = self.subtree_sum(self.root, sum);
print("\n", terminator: "");
}
}
}
func main()
{
// Create tree object
let tree: BinaryTree = BinaryTree();
// Binary Tree
// -----------------------
// 5
// / \
// 3 -2
// / \ / \
// 2 2 2 10
// / / \ / \
// 1 -4 2 1 -5
//
//
// Add nodes
tree.root = Node(5);
tree.root!.left = Node(3);
tree.root!.right = Node(-2);
tree.root!.right!.right = Node(10);
tree.root!.right!.right!.left = Node(1);
tree.root!.right!.right!.right = Node(-5);
tree.root!.right!.left = Node(2);
tree.root!.left!.left = Node(2);
tree.root!.left!.left!.left = Node(1);
tree.root!.left!.right = Node(2);
tree.root!.left!.right!.left = Node(-4);
tree.root!.left!.right!.right = Node(2);
let sum: Int = 6;
tree.subtree(sum);
}
main();
Output
Subtree of sum 6 are
1 2 3 -4 2 2
1 10 -5
2 -2 1 10 -5
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