TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Program to Find the Sum of all the Nodes of a Binary Tree

Program to Find the Sum of all the Nodes of a Binary Tree on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

<< Back to PROGRAM

Q. Program to find the sum of all the nodes of a Binary Tree

Explanation

In this program, we need to calculate the sum of nodes present in the binary tree. First, we will traverse through the left sub-tree and calculate the sum of nodes present in the left sub-tree. Similarly, we calculate the sum of nodes present in the right sub-tree and calculate total sum by adding the root?s data.

Program to find the sum of all the nodes of a Binary Tree

For the given tree, sum of nodes of the binary tree will be 1 + 2 + 5 + 8 + 6 + 9 = 31.

Algorithm

  1. Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
  3. Define another class which has an attribute root.
    1. Root represents the root node of the tree and initialize it to null.
  4. calculateSum() will calculate the sum of nodes present in the binary tree:
    1. It checks whether the root is null, which means that the tree is empty.
    2. If the tree is not empty, traverse through left subtree, calculate the sum of nodes and store it in sumLeft.
    3. Then, traverse through the right subtree, calculate the sum of nodes and store it in sumRight.
    4. Finally, calculate total sum = temp.data + sumLeft + sumRight.

Solution

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class SumOfNodes:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
    
    #calculateSum() will calculate the sum of all the nodes present in the binary tree
    def calculateSum(self, temp):
        sum = sumRight = sumLeft = 0;
        
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty");
            return 0;
        else:
            #Calculate the sum of nodes present in left subtree
            if(temp.left != None):
                sumLeft = self.calculateSum(temp.left);
            
            #Calculate the sum of nodes present in right subtree
            if(temp.right != None):
                sumRight = self.calculateSum(temp.right);
            
            #Calculate the sum of all nodes by adding sumLeft, sumRight and root node's data
            sum = temp.data + sumLeft + sumRight; 
        return sum;
 
bt = SumOfNodes();
#Add nodes to the binary tree
bt.root = Node(5);
bt.root.left = Node(2);
bt.root.right = Node(9);
bt.root.left.left = Node(1);
bt.root.right.left = Node(8);
bt.root.right.right = Node(6);
 
#Display the sum of all the nodes in the given binary tree
print("Sum of all nodes of binary tree: " + str(bt.calculateSum(bt.root)));

Output:

Sum of all nodes of binary tree: 31

C

#include <stdio.h>
#include <stdlib.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//calculateSum() will calculate the sum of all the nodes present in the binary tree
int calculateSum(struct node *temp){
    int sum, sumLeft, sumRight;
    sum = sumRight = sumLeft = 0;
    
    //Check whether tree is empty
    if(root == NULL) {
        printf("Tree is empty\n");
        return 0;
    }
    else {
        //Calculate the sum of nodes present in left subtree
        if(temp->left != NULL)
            sumLeft = calculateSum(temp->left);
        
        //Calculate the sum of nodes present in right subtree
        if(temp->right != NULL)
              sumRight = calculateSum(temp->right);
        
        //Calculate the sum of all nodes by adding sumLeft, sumRight and root node's data
        sum = temp->data + sumLeft + sumRight; 
        return sum;
  }    
}
 
int main()
{
    //Add nodes to the binary tree
    root = createNode(5);
    root->left = createNode(2);
    root->right = createNode(9);
    root->left->left = createNode(1);
    root->right->left = createNode(8);
    root->right->right = createNode(6);
    
    //Display the sum of all the nodes in the given binary tree
    printf("Sum of all nodes of binary tree: %d", calculateSum(root));
    return 0;
}

Output:

Sum of all nodes of binary tree: 31

JAVA

public class SumOfNodes {
      
      //Represent the node of binary tree
        public static class Node{
        int data;
        Node left;
        Node right;
        
        public Node(int data){
            //Assign data to the new node, set left and right children to null
            this.data = data;
            this.left = null;
            this.right = null;
        }
      }
      
      //Represent the root of binary tree
      public Node root;
      
      public SumOfNodes(){
        root = null;
      }
      
      //calculateSum() will calculate the sum of all the nodes present in the binary tree
      public int calculateSum(Node temp){
        int sum, sumLeft, sumRight;
        sum = sumRight = sumLeft = 0;
        
        //Check whether tree is empty
        if(root == null) {
            System.out.println("Tree is empty");
            return 0;
        }
        else {
            //Calculate the sum of nodes present in left subtree
            if(temp.left != null)
                sumLeft = calculateSum(temp.left);
            
            //Calculate the sum of nodes present in right subtree
            if(temp.right != null)
                sumRight = calculateSum(temp.right);
            
            //Calculate the sum of all nodes by adding sumLeft, sumRight and root node's data
            sum = temp.data + sumLeft + sumRight; 
            return sum;
        }    
      }
      
      public static void main(String[] args) {
        
        SumOfNodes bt = new SumOfNodes();
        //Add nodes to the binary tree
        bt.root = new Node(5);
        bt.root.left = new Node(2);
        bt.root.right = new Node(9);
        bt.root.left.left = new Node(1);
        bt.root.right.left = new Node(8);
        bt.root.right.right = new Node(6);
        
        //Display the sum of all the nodes in the given binary tree
        System.out.println("Sum of all nodes of binary tree: " + bt.calculateSum(bt.root));
      }
    }

Output:

Sum of all nodes of binary tree: 31

C#

using System;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class SumOfNodes<T>{
            //Represent the root of binary tree
            public Node<T> root;
 
            public static Boolean flag = false;
 
            public SumOfNodes(){
                root = null;
            }
        
        //calculateSum() will calculate the sum of all the nodes present in the binary tree
          public int calculateSum(Node<T> temp){
            int sum, sumLeft, sumRight;
            sum = sumRight = sumLeft = 0;
            
            //Check whether tree is empty
            if(root == null) {
                Console.WriteLine("Tree is empty");
                return 0;
            }
            else {
                //Calculate the sum of nodes present in left subtree
                if(temp.left != null)
                    sumLeft = calculateSum(temp.left);
                
                //Calculate the sum of nodes present in right subtree
                if(temp.right != null)
                    sumRight = calculateSum(temp.right);
                
                //Calculate the sum of all nodes by adding sumLeft, sumRight and root node's data
                sum = (int)(object)temp.data + sumLeft + sumRight; 
                return sum;
            }    
          }
    }    
        public static void Main()
        {
            SumOfNodes<int> bt = new SumOfNodes<int>();
            //Add nodes to the binary tree
            bt.root = new Node<int>(5);
            bt.root.left = new Node<int>(2);
            bt.root.right = new Node<int>(9);
            bt.root.left.left = new Node<int>(1);
            bt.root.right.left = new Node<int>(8);
            bt.root.right.right = new Node<int>(6);
            
            //Display the sum of all the nodes in the given binary tree
            Console.WriteLine("Sum of all nodes of binary tree: " + bt.calculateSum(bt.root));            
        }    
    }
}

Output:

Sum of all nodes of binary tree: 31

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class SumOfNodes{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //calculateSum() will calculate the sum of all the nodes present in the binary tree
    function calculateSum($temp){
        $sum = 0;
        $sumLeft = 0;
        $sumRight = 0;
      
        //Check whether tree is empty
        if($this->root == NULL) {
            print "Tree is empty <br>";
            return 0;
        }
        else {
             //Calculate the sum of nodes present in left subtree
            if($temp->left != NULL)
                $sumLeft = $this->calculateSum($temp->left);
 
             //Calculate the sum of nodes present in right subtree
            if($temp->right != NULL)
                $sumRight = $this->calculateSum($temp->right);
 
             //Calculate the sum of all nodes by adding sumLeft, sumRight and root node's data
             $sum = $temp->data + $sumLeft + $sumRight; 
             return $sum;
      }    
    }
}
$bt = new SumOfNodes();
//Add nodes to the binary tree
$bt->root = new Node(5);
$bt->root->left = new Node(2);
$bt->root->right = new Node(9);
$bt->root->left->left = new Node(1);
$bt->root->right->left = new Node(8);
$bt->root->right->right = new Node(6);
 
//Display the sum of all the nodes in the given binary tree
print "Sum of all nodes of binary tree: " . $bt->calculateSum($bt->root);
?>
</body>
</html>

Output:

Sum of all nodes of binary tree: 31

Next TopicPrograms List




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf