Sum of all nodes in a binary tree

By using recursion we can easily find the sum of binary tree nodes. When tree node contains integer values. Let see an example.

/*
    C Program 
    Sum of all nodes in a binary tree
    Recursive solution
*/
#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 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 preorder elements
void preorder(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		preorder(node->left);
		preorder(node->right);
	}
}

//Return the sum of nodes in binary tree
int node_sum(struct Node *node)
{
	if (node == NULL)
	{
		return 0;
	}
	// Add nodes
	return (node->data) + node_sum(node->left) + node_sum(node->right);
}

int main()
{
	struct Node *root = NULL;
	/*
	constructor binary tree
	-----------------
	     6                            
	   /   \    
	  2     3     
	 / \      \               
	8  -7      1
	   /      /  \
	  6      4    5
	.................
	*/
	root = get_node(6);
	root->left = get_node(2);
	root->left->left = get_node(8);
	root->left->right = get_node(-7);
	root->left->right->left = get_node(6);
	root->right = get_node(3);
	root->right->right = get_node(1);
	root->right->right->left = get_node(4);
	root->right->right->right = get_node(5);
	printf("\n Tree Nodes : ");
	preorder(root);
	printf("\n Sum : %d\n", node_sum(root));
	return 0;
}

Output

 Tree Nodes :   6  2  8  -7  6  3  1  4  5
 Sum : 28
/*
    Java Program 
    Sum of all nodes in a binary tree
    Recursive solution
*/
//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 preorder elements
	public void preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//Return the sum of nodes in binary tree
	public int node_sum(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		// Add nodes
		return (node.data) + node_sum(node.left) + node_sum(node.right);
	}
	public static void main(String[] args)
	{
		//Make object of binary tree
		BinaryTree tree = new BinaryTree();
		/*
		    constructor binary tree
		    -----------------
		         6                            
		       /   \    
		      2     3     
		     / \      \               
		    8  -7      1
		       /      /  \
		      6      4    5
		    .................
		*/
		tree.root = new Node(6);
		tree.root.left = new Node(2);
		tree.root.left.left = new Node(8);
		tree.root.left.right = new Node(-7);
		tree.root.left.right.left = new Node(6);
		tree.root.right = new Node(3);
		tree.root.right.right = new Node(1);
		tree.root.right.right.left = new Node(4);
		tree.root.right.right.right = new Node(5);
		System.out.print("\n Tree Nodes : ");
		tree.preorder(tree.root);
		System.out.print("\n Sum : " + tree.node_sum(tree.root) + "\n");
	}
}

Output

 Tree Nodes :   6  2  8  -7  6  3  1  4  5
 Sum : 28
//Include header file
#include <iostream>
using namespace std;

/*
    C++ Program 
    Sum of all nodes in a binary tree
    Recursive solution
*/

//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 preorder elements
	void preorder(Node *node)
	{
		if (node != NULL)
		{
			//Print node value
			cout << "  " << node->data;
			this->preorder(node->left);
			this->preorder(node->right);
		}
	}
	//Return the sum of nodes in binary tree
	int node_sum(Node *node)
	{
		if (node == NULL)
		{
			return 0;
		}
		// Add nodes
		return (node->data) + this->node_sum(node->left) + this->node_sum(node->right);
	}
};
int main()
{
	//Make object of binary tree
	BinaryTree tree = BinaryTree();
	/*
			    constructor binary tree
			    -----------------
			         6                            
			       /   \    
			      2     3     
			     / \      \               
			    8  -7      1
			       /      /  \
			      6      4    5
			    .................
			*/
	tree.root = new Node(6);
	tree.root->left = new Node(2);
	tree.root->left->left = new Node(8);
	tree.root->left->right = new Node(-7);
	tree.root->left->right->left = new Node(6);
	tree.root->right = new Node(3);
	tree.root->right->right = new Node(1);
	tree.root->right->right->left = new Node(4);
	tree.root->right->right->right = new Node(5);
	cout << "\n Tree Nodes : ";
	tree.preorder(tree.root);
	cout << "\n Sum : " << tree.node_sum(tree.root) << "\n";
	return 0;
}

Output

 Tree Nodes :   6  2  8  -7  6  3  1  4  5
 Sum : 28
//Include namespace system
using System;

/*
    C# Program 
    Sum of all nodes in a binary tree
    Recursive solution
*/

//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 preorder elements
	public void preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			Console.Write("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//Return the sum of nodes in binary tree
	public int node_sum(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		// Add nodes
		return (node.data) + node_sum(node.left) + node_sum(node.right);
	}
	public static void Main(String[] args)
	{
		//Make object of binary tree
		BinaryTree tree = new BinaryTree();
		/*
				    constructor binary tree
				    -----------------
				         6                            
				       /   \    
				      2     3     
				     / \      \               
				    8  -7      1
				       /      /  \
				      6      4    5
				    .................
				*/
		tree.root = new Node(6);
		tree.root.left = new Node(2);
		tree.root.left.left = new Node(8);
		tree.root.left.right = new Node(-7);
		tree.root.left.right.left = new Node(6);
		tree.root.right = new Node(3);
		tree.root.right.right = new Node(1);
		tree.root.right.right.left = new Node(4);
		tree.root.right.right.right = new Node(5);
		Console.Write("\n Tree Nodes : ");
		tree.preorder(tree.root);
		Console.Write("\n Sum : " + tree.node_sum(tree.root) + "\n");
	}
}

Output

 Tree Nodes :   6  2  8  -7  6  3  1  4  5
 Sum : 28
<?php
/*
    Php Program 
    Sum of all nodes in a binary tree
    Recursive solution
*/
//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 preorder elements
	public	function preorder($node)
	{
		if ($node != null)
		{
			//Print node value
			echo "  ". $node->data;
			$this->preorder($node->left);
			$this->preorder($node->right);
		}
	}
	//Return the sum of nodes in binary tree
	public	function node_sum($node)
	{
		if ($node == null)
		{
			return 0;
		}
		// Add nodes
		return ($node->data) + $this->node_sum($node->left) + $this->node_sum($node->right);
	}
}

function main()
{
	//Make object of binary tree
	$tree = new BinaryTree();
	/*
			    constructor binary tree
			    -----------------
			         6                            
			       /   \    
			      2     3     
			     / \      \               
			    8  -7      1
			       /      /  \
			      6      4    5
			    .................
			*/
	$tree->root = new Node(6);
	$tree->root->left = new Node(2);
	$tree->root->left->left = new Node(8);
	$tree->root->left->right = new Node(-7);
	$tree->root->left->right->left = new Node(6);
	$tree->root->right = new Node(3);
	$tree->root->right->right = new Node(1);
	$tree->root->right->right->left = new Node(4);
	$tree->root->right->right->right = new Node(5);
	echo "\n Tree Nodes : ";
	$tree->preorder($tree->root);
	echo "\n Sum : ". $tree->node_sum($tree->root) ."\n";
}
main();

Output

 Tree Nodes :   6  2  8  -7  6  3  1  4  5
 Sum : 28
/*
    Node Js Program 
    Sum of all nodes in a binary tree
    Recursive solution
*/

//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 preorder elements
	preorder(node)
	{
		if (node != null)
		{
			//Print node value
			process.stdout.write("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	//Return the sum of nodes in binary tree
	node_sum(node)
	{
		if (node == null)
		{
			return 0;
		}
		// Add nodes
		return (node.data) + this.node_sum(node.left) + this.node_sum(node.right);
	}
}

function main()
{
	//Make object of binary tree
	var tree = new BinaryTree();
	/*
			    constructor binary tree
			    -----------------
			         6                            
			       /   \    
			      2     3     
			     / \      \               
			    8  -7      1
			       /      /  \
			      6      4    5
			    .................
			*/
	tree.root = new Node(6);
	tree.root.left = new Node(2);
	tree.root.left.left = new Node(8);
	tree.root.left.right = new Node(-7);
	tree.root.left.right.left = new Node(6);
	tree.root.right = new Node(3);
	tree.root.right.right = new Node(1);
	tree.root.right.right.left = new Node(4);
	tree.root.right.right.right = new Node(5);
	process.stdout.write("\n Tree Nodes : ");
	tree.preorder(tree.root);
	process.stdout.write("\n Sum : " + tree.node_sum(tree.root) + "\n");
}
main();

Output

 Tree Nodes :   6  2  8  -7  6  3  1  4  5
 Sum : 28
#     Python 3 Program 
#     Sum of all nodes in a binary tree
#     Recursive solution

# 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 preorder elements
	def preorder(self, node) :
		if (node != None) :
			# Print node value
			print("  ", node.data, end = "")
			self.preorder(node.left)
			self.preorder(node.right)
		
	
	# Return the sum of nodes in binary tree
	def node_sum(self, node) :
		if (node == None) :
			return 0
		
		#  Add nodes
		return (node.data) + self.node_sum(node.left) + self.node_sum(node.right)
	

def main() :
	# Make object of binary tree
	tree = BinaryTree()
	# 
	# 		    constructor binary tree
	# 		    -----------------
	# 		         6                            
	# 		       /   \    
	# 		      2     3     
	# 		     / \      \               
	# 		    8  -7      1
	# 		       /      /  \
	# 		      6      4    5
	# 		    .................
	# 		
	
	tree.root = Node(6)
	tree.root.left = Node(2)
	tree.root.left.left = Node(8)
	tree.root.left.right = Node(-7)
	tree.root.left.right.left = Node(6)
	tree.root.right = Node(3)
	tree.root.right.right = Node(1)
	tree.root.right.right.left = Node(4)
	tree.root.right.right.right = Node(5)
	print("\n Tree Nodes : ", end = "")
	tree.preorder(tree.root)
	print("\n Sum : ", tree.node_sum(tree.root) ,"\n", end = "")

if __name__ == "__main__": main()

Output

 Tree Nodes :    6   2   8   -7   6   3   1   4   5
 Sum :  28
#     Ruby Program 
#     Sum of all nodes in a binary tree
#     Recursive solution

# 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 preorder elements
	def preorder(node) 
		if (node != nil) 
			# Print node value
			print("  ", node.data)
			self.preorder(node.left)
			self.preorder(node.right)
		end

	end

	# Return the sum of nodes in binary tree
	def node_sum(node) 
		if (node == nil) 
			return 0
		end

		#  Add nodes
		return (node.data) + self.node_sum(node.left) + self.node_sum(node.right)
	end

end

def main() 
	# Make object of binary tree
	tree = BinaryTree.new()
	# 
	# 		    constructor binary tree
	# 		    -----------------
	# 		         6                            
	# 		       /   \    
	# 		      2     3     
	# 		     / \      \               
	# 		    8  -7      1
	# 		       /      /  \
	# 		      6      4    5
	# 		    .................
	# 		
	
	tree.root = Node.new(6)
	tree.root.left = Node.new(2)
	tree.root.left.left = Node.new(8)
	tree.root.left.right = Node.new(-7)
	tree.root.left.right.left = Node.new(6)
	tree.root.right = Node.new(3)
	tree.root.right.right = Node.new(1)
	tree.root.right.right.left = Node.new(4)
	tree.root.right.right.right = Node.new(5)
	print("\n Tree Nodes : ")
	tree.preorder(tree.root)
	print("\n Sum : ", tree.node_sum(tree.root) ,"\n")
end

main()

Output

 Tree Nodes :   6  2  8  -7  6  3  1  4  5
 Sum : 28
/*
    Scala Program 
    Sum of all nodes in a binary tree
    Recursive solution
*/

//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 preorder elements
	def preorder(node: Node): Unit = {
		if (node != null)
		{
			//Print node value
			print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//Return the sum of nodes in binary tree
	def node_sum(node: Node): Int = {
		if (node == null)
		{
			return 0;
		}
		// Add nodes
		return (node.data) + node_sum(node.left) + node_sum(node.right);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object of binary tree
		var tree: BinaryTree = new BinaryTree();
		/*
				    constructor binary tree
				    -----------------
				         6                            
				       /   \    
				      2     3     
				     / \      \               
				    8  -7      1
				       /      /  \
				      6      4    5
				    .................
				*/
		tree.root = new Node(6);
		tree.root.left = new Node(2);
		tree.root.left.left = new Node(8);
		tree.root.left.right = new Node(-7);
		tree.root.left.right.left = new Node(6);
		tree.root.right = new Node(3);
		tree.root.right.right = new Node(1);
		tree.root.right.right.left = new Node(4);
		tree.root.right.right.right = new Node(5);
		print("\n Tree Nodes : ");
		tree.preorder(tree.root);
		print("\n Sum : " + tree.node_sum(tree.root) + "\n");
	}
}

Output

 Tree Nodes :   6  2  8  -7  6  3  1  4  5
 Sum : 28
/*
    Swift 4 Program 
    Sum of all nodes in a binary tree
    Recursive solution
*/

//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 preorder elements
	func preorder(_ node: Node? )
	{
		if (node != nil)
		{
			//Print node value
			print("  ", node!.data, terminator: "");
			self.preorder(node!.left);
			self.preorder(node!.right);
		}
	}
	//Return the sum of nodes in binary tree
	func node_sum(_ node: Node? )->Int
	{
		if (node == nil)
		{
			return 0;
		}
		// Add nodes
		return (node!.data) + self.node_sum(node!.left) + self.node_sum(node!.right);
	}
}
func main()
{
	//Make object of binary tree
	let tree: BinaryTree = BinaryTree();
	/*
			    constructor binary tree
			    -----------------
			         6                            
			       /   \    
			      2     3     
			     / \      \               
			    8  -7      1
			       /      /  \
			      6      4    5
			    .................
	*/
	tree.root = Node(6);
	tree.root!.left = Node(2);
	tree.root!.left!.left = Node(8);
	tree.root!.left!.right = Node(-7);
	tree.root!.left!.right!.left = Node(6);
	tree.root!.right = Node(3);
	tree.root!.right!.right = Node(1);
	tree.root!.right!.right!.left = Node(4);
	tree.root!.right!.right!.right = Node(5);
	print("\n Tree Nodes : ", terminator: "");
	tree.preorder(tree.root);
	print("\n Sum : ", tree.node_sum(tree.root) );
}
main();

Output

 Tree Nodes :    6   2   8   -7   6   3   1   4   5
 Sum :  28

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







© 2021, kalkicode.com, All rights reserved