Convert given binary tree to its sum tree
In computer science, a binary tree is a tree data structure in which each node can have at most two children, typically referred to as the left child and the right child. In a sum tree, each node's value is equal to the sum of its left and right subtree's values.
Converting a binary tree to its sum tree means modifying the original tree such that each node's value is replaced by the sum of the values of its left and right subtrees. Specifically, for each node in the tree, the new value of the node will be the sum of the values of its left and right subtrees plus the value of the node itself.
This transformation can be done recursively by visiting each node in the binary tree and updating its value according to the sum of its subtrees. Once the transformation is complete, the resulting binary tree will be a sum tree, where each node's value is the sum of its children's values.
Program Solution
/*
C Program
In-place convert given binary tree to its sum tree
*/
#include <stdio.h>
#include <stdlib.h>
//Structure of Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node *insert(int data)
{
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set node value
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
printf("Memory Overflow\n");
}
//return reference
return new_node;
}
//Display tree element preorder form
void preorder(struct Node *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
//Transform binary tree to its sum tree
int sum_tree(struct Node *node)
{
if (node != NULL)
{
int a = sum_tree(node->left);
int b = sum_tree(node->right);
int current = node->data;
// Change node data
node->data = a + b;
if (node->left == NULL && node->right == NULL)
{
// When node is leaf
return current;
}
else
{
return a + b + current;
}
}
else
{
return 0;
}
}
int main()
{
struct Node *root = NULL;
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 4 5
/ \
7 -2
*/
//Add binary tree nodes
root = insert(1);
root->left = insert(6);
root->left->left = insert(2);
root->right = insert(8);
root->right->right = insert(5);
root->right->left = insert(4);
root->right->left->right = insert(-2);
root->left->right = insert(3);
root->left->left->left = insert(7);
printf(" Before Convert\n");
preorder(root);
//Convert to its sum tree
sum_tree(root);
/*
Converted sum tree
-----------------------
33
/ \
/ \
/ \
12 7
/ \ / \
7 0 -2 0
/ \
0 0
*/
printf("\n After Convert \n");
preorder(root);
return 0;
}
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
/*
Java Program
In-place convert given binary tree to its sum 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;
}
}
class BinaryTree
{
public Node root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Display tree elements in preorder form
public void preorder(Node node)
{
if (node != null)
{
// Print node value
System.out.print(" " + node.data + " ");
preorder(node.left);
preorder(node.right);
}
}
// Transform binary tree to its sum tree
public int sum_tree(Node node)
{
if (node != null)
{
int a = sum_tree(node.left);
int b = sum_tree(node.right);
int current = node.data;
// Change node data
node.data = a + b;
if (node.left == null && node.right == null)
{
// When node is leaf
return current;
}
else
{
return a + b + current;
}
}
else
{
return 0;
}
}
public static void main(String[] args)
{
// Make object of binary tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 4 5
/ \
7 -2
*/
//Add binary tree nodes
tree.root = new Node(1);
tree.root.left = new Node(6);
tree.root.left.left = new Node(2);
tree.root.right = new Node(8);
tree.root.right.right = new Node(5);
tree.root.right.left = new Node(4);
tree.root.right.left.right = new Node(-2);
tree.root.left.right = new Node(3);
tree.root.left.left.left = new Node(7);
System.out.print(" Before Convert\n");
tree.preorder(tree.root);
//Convert to its sum tree
tree.sum_tree(tree.root);
/*
Converted sum tree
-----------------------
33
/ \
/ \
/ \
12 7
/ \ / \
7 0 -2 0
/ \
0 0
*/
System.out.print("\n After Convert \n");
tree.preorder(tree.root);
}
}
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
//Include header file
#include <iostream>
using namespace std;
/*
C++ Program
In-place convert given binary tree to its sum 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;
BinaryTree()
{
// Set initial tree root to null
this->root = NULL;
}
// Display tree elements in preorder form
void preorder(Node *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data << " ";
this->preorder(node->left);
this->preorder(node->right);
}
}
// Transform binary tree to its sum tree
int sum_tree(Node *node)
{
if (node != NULL)
{
int a = this->sum_tree(node->left);
int b = this->sum_tree(node->right);
int current = node->data;
// Change node data
node->data = a + b;
if (node->left == NULL && node->right == NULL)
{
// When node is leaf
return current;
}
else
{
return a + b + current;
}
}
else
{
return 0;
}
}
};
int main()
{
// Make object of binary tree
BinaryTree tree = BinaryTree();
tree.root = new Node(1);
tree.root->left = new Node(6);
tree.root->left->left = new Node(2);
tree.root->right = new Node(8);
tree.root->right->right = new Node(5);
tree.root->right->left = new Node(4);
tree.root->right->left->right = new Node(-2);
tree.root->left->right = new Node(3);
tree.root->left->left->left = new Node(7);
cout << " Before Convert\n";
tree.preorder(tree.root);
//Convert to its sum tree
tree.sum_tree(tree.root);
/*
Converted sum tree
-----------------------
33
/ \
/ \
/ \
12 7
/ \ / \
7 0 -2 0
/ \
0 0
*/
cout << "\n After Convert \n";
tree.preorder(tree.root);
return 0;
}
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
//Include namespace system
using System;
/*
C# Program
In-place convert given binary tree to its sum 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;
}
}
class BinaryTree
{
public Node root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Display tree elements in preorder form
public void preorder(Node node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data + " ");
preorder(node.left);
preorder(node.right);
}
}
// Transform binary tree to its sum tree
public int sum_tree(Node node)
{
if (node != null)
{
int a = sum_tree(node.left);
int b = sum_tree(node.right);
int current = node.data;
// Change node data
node.data = a + b;
if (node.left == null && node.right == null)
{
// When node is leaf
return current;
}
else
{
return a + b + current;
}
}
else
{
return 0;
}
}
public static void Main(String[] args)
{
// Make object of binary tree
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(6);
tree.root.left.left = new Node(2);
tree.root.right = new Node(8);
tree.root.right.right = new Node(5);
tree.root.right.left = new Node(4);
tree.root.right.left.right = new Node(-2);
tree.root.left.right = new Node(3);
tree.root.left.left.left = new Node(7);
Console.Write(" Before Convert\n");
tree.preorder(tree.root);
//Convert to its sum tree
tree.sum_tree(tree.root);
/*
Converted sum tree
-----------------------
33
/ \
/ \
/ \
12 7
/ \ / \
7 0 -2 0
/ \
0 0
*/
Console.Write("\n After Convert \n");
tree.preorder(tree.root);
}
}
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
<?php
/*
Php Program
In-place convert given binary tree to its sum 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;
function __construct()
{
// Set initial tree root to null
$this->root = null;
}
// Display tree elements in preorder form
public function preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data ." ";
$this->preorder($node->left);
$this->preorder($node->right);
}
}
// Transform binary tree to its sum tree
public function sum_tree($node)
{
if ($node != null)
{
$a = $this->sum_tree($node->left);
$b = $this->sum_tree($node->right);
$current = $node->data;
// Change node data
$node->data = $a + $b;
if ($node->left == null && $node->right == null)
{
// When node is leaf
return $current;
}
else
{
return $a + $b + $current;
}
}
else
{
return 0;
}
}
}
function main()
{
// Make object of binary tree
$tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 4 5
/ \
7 -2
*/
//Add binary tree nodes
$tree->root = new Node(1);
$tree->root->left = new Node(6);
$tree->root->left->left = new Node(2);
$tree->root->right = new Node(8);
$tree->root->right->right = new Node(5);
$tree->root->right->left = new Node(4);
$tree->root->right->left->right = new Node(-2);
$tree->root->left->right = new Node(3);
$tree->root->left->left->left = new Node(7);
echo " Before Convert\n";
$tree->preorder($tree->root);
//Convert to its sum tree
$tree->sum_tree($tree->root);
/*
Converted sum tree
-----------------------
33
/ \
/ \
/ \
12 7
/ \ / \
7 0 -2 0
/ \
0 0
*/
echo "\n After Convert \n";
$tree->preorder($tree->root);
}
main();
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
/*
Node Js Program
In-place convert given binary tree to its sum 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;
}
// Display tree elements in preorder form
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data + " ");
this.preorder(node.left);
this.preorder(node.right);
}
}
// Transform binary tree to its sum tree
sum_tree(node)
{
if (node != null)
{
var a = this.sum_tree(node.left);
var b = this.sum_tree(node.right);
var current = node.data;
// Change node data
node.data = a + b;
if (node.left == null && node.right == null)
{
// When node is leaf
return current;
}
else
{
return a + b + current;
}
}
else
{
return 0;
}
}
}
function main()
{
// Make object of binary tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 4 5
/ \
7 -2
*/
//Add binary tree nodes
tree.root = new Node(1);
tree.root.left = new Node(6);
tree.root.left.left = new Node(2);
tree.root.right = new Node(8);
tree.root.right.right = new Node(5);
tree.root.right.left = new Node(4);
tree.root.right.left.right = new Node(-2);
tree.root.left.right = new Node(3);
tree.root.left.left.left = new Node(7);
process.stdout.write(" Before Convert\n");
tree.preorder(tree.root);
//Convert to its sum tree
tree.sum_tree(tree.root);
/*
Converted sum tree
-----------------------
33
/ \
/ \
/ \
12 7
/ \ / \
7 0 -2 0
/ \
0 0
*/
process.stdout.write("\n After Convert \n");
tree.preorder(tree.root);
}
main();
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
# Python3 Program
# In-place convert given binary tree to its sum 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
# Display tree elements in preorder form
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data ," ", end = "")
self.preorder(node.left)
self.preorder(node.right)
# Transform binary tree to its sum tree
def sum_tree(self, node) :
if (node != None) :
a = self.sum_tree(node.left)
b = self.sum_tree(node.right)
current = node.data
# Change node data
node.data = a + b
if (node.left == None and node.right == None) :
# When node is leaf
return current
else :
return a + b + current
else :
return 0
def main() :
# Make object of binary tree
tree = BinaryTree()
#
# Construct Binary Tree
# -----------------------
# 1
# / \
# 6 8
# / \ / \
# 2 3 4 5
# / \
# 7 -2
#
#
# Add binary tree nodes
tree.root = Node(1)
tree.root.left = Node(6)
tree.root.left.left = Node(2)
tree.root.right = Node(8)
tree.root.right.right = Node(5)
tree.root.right.left = Node(4)
tree.root.right.left.right = Node(-2)
tree.root.left.right = Node(3)
tree.root.left.left.left = Node(7)
print(" Before Convert\n", end = "")
tree.preorder(tree.root)
# Convert to its sum tree
tree.sum_tree(tree.root)
#
# Converted sum tree
# -----------------------
# 33
# / \
# / \
# / \
# 12 7
# / \ / \
# 7 0 -2 0
# / \
# 0 0
#
print("\n After Convert \n", end = "")
tree.preorder(tree.root)
if __name__ == "__main__": main()
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
# Ruby Program
# In-place convert given binary tree to its sum 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
attr_accessor :root
def initialize()
# Set initial tree root to null
self.root = nil
end
# Display tree elements in preorder form
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data ," ")
self.preorder(node.left)
self.preorder(node.right)
end
end
# Transform binary tree to its sum tree
def sum_tree(node)
if (node != nil)
a = self.sum_tree(node.left)
b = self.sum_tree(node.right)
current = node.data
# Change node data
node.data = a + b
if (node.left == nil && node.right == nil)
# When node is leaf
return current
else
return a + b + current
end
else
return 0
end
end
end
def main()
# Make object of binary tree
tree = BinaryTree.new()
#
# Construct Binary Tree
# -----------------------
# 1
# / \
# 6 8
# / \ / \
# 2 3 4 5
# / \
# 7 -2
#
#
# Add binary tree nodes
tree.root = Node.new(1)
tree.root.left = Node.new(6)
tree.root.left.left = Node.new(2)
tree.root.right = Node.new(8)
tree.root.right.right = Node.new(5)
tree.root.right.left = Node.new(4)
tree.root.right.left.right = Node.new(-2)
tree.root.left.right = Node.new(3)
tree.root.left.left.left = Node.new(7)
print(" Before Convert\n")
tree.preorder(tree.root)
# Convert to its sum tree
tree.sum_tree(tree.root)
#
# Converted sum tree
# -----------------------
# 33
# / \
# / \
# / \
# 12 7
# / \ / \
# 7 0 -2 0
# / \
# 0 0
#
print("\n After Convert \n")
tree.preorder(tree.root)
end
main()
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
/*
Scala Program
In-place convert given binary tree to its sum 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)
{
def this()
{
this(null);
}
// Display tree elements in preorder form
def preorder(node: Node): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data + " ");
preorder(node.left);
preorder(node.right);
}
}
// Transform binary tree to its sum tree
def sum_tree(node: Node): Int = {
if (node != null)
{
var a: Int = sum_tree(node.left);
var b: Int = sum_tree(node.right);
var current: Int = node.data;
// Change node data
node.data = a + b;
if (node.left == null && node.right == null)
{
// When node is leaf
return current;
}
else
{
return a + b + current;
}
}
else
{
return 0;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Make object of binary tree
var tree: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 4 5
/ \
7 -2
*/
//Add binary tree nodes
tree.root = new Node(1);
tree.root.left = new Node(6);
tree.root.left.left = new Node(2);
tree.root.right = new Node(8);
tree.root.right.right = new Node(5);
tree.root.right.left = new Node(4);
tree.root.right.left.right = new Node(-2);
tree.root.left.right = new Node(3);
tree.root.left.left.left = new Node(7);
print(" Before Convert\n");
tree.preorder(tree.root);
//Convert to its sum tree
tree.sum_tree(tree.root);
/*
Converted sum tree
-----------------------
33
/ \
/ \
/ \
12 7
/ \ / \
7 0 -2 0
/ \
0 0
*/
print("\n After Convert \n");
tree.preorder(tree.root);
}
}
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
/*
Swift 4 Program
In-place convert given binary tree to its sum 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? ;
init()
{
// Set initial tree root to null
self.root = nil;
}
// Display tree elements in preorder form
func preorder(_ node: Node? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data ," ", terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
// Transform binary tree to its sum tree
func sum_tree(_ node: Node? ) -> Int
{
if (node != nil)
{
let a: Int = self.sum_tree(node!.left);
let b: Int = self.sum_tree(node!.right);
let current: Int = node!.data;
// Change node data
node!.data = a + b;
if (node!.left == nil && node!.right == nil)
{
// When node is leaf
return current;
}
else
{
return a + b + current;
}
}
else
{
return 0;
}
}
}
func main()
{
// Make object of binary tree
let tree: BinaryTree = BinaryTree();
tree.root = Node(1);
tree.root!.left = Node(6);
tree.root!.left!.left = Node(2);
tree.root!.right = Node(8);
tree.root!.right!.right = Node(5);
tree.root!.right!.left = Node(4);
tree.root!.right!.left!.right = Node(-2);
tree.root!.left!.right = Node(3);
tree.root!.left!.left!.left = Node(7);
print(" Before Convert\n", terminator: "");
tree.preorder(tree.root);
//Convert to its sum tree
let _ = tree.sum_tree(tree.root);
/*
Converted sum tree
-----------------------
33
/ \
/ \
/ \
12 7
/ \ / \
7 0 -2 0
/ \
0 0
*/
print("\n After Convert \n", terminator: "");
tree.preorder(tree.root);
}
main();
Output
Before Convert
1 6 2 7 3 8 4 -2 5
After Convert
33 12 7 0 0 7 -2 0 0
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