Skip to main content

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
Last updated on by Kalkicode




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