Convert given binary tree to its sum tree

Here given code implementation process.

``````/*
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

*/
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

*/
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

*/
\$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

*/
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
#
#

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_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_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
#
#

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

*/
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``````

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.