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

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

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.
When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
Define another class which has an attribute root.
1. Root represents the root node of the tree and initialize it to null.
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 emptyn”);          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

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

Explanation

Algorithm

Solution

Python

C

JAVA

C#

PHP

Potential Energy

Program to Find The Transpose of a Given Matrix

You may also like