Sum of Leaf Node at each Horizontal Level of Binary Tree

Yogesh Kumar
Last Updated: May 13, 2022

Problem Statement

We have given a Binary Tree; then, we have to find the sum of leaf nodes at each horizontal level of the Tree.

If the leaf node is found at every level, we have to accumulate the sum of all the leaf nodes of that particular level and print it. Let’s understand it with the help of an example. 

 

Image Source:- Tree

 

Here is the given Binary Tree:- 

Sum of all the leaf nodes at every horizontal level

Sum Value at each HORIZONTAL LEVEL 1:- 0.

Sum Value at each HORIZONTAL LEVEL 2:- 15.

Sum Value at each HORIZONTAL LEVEL 3:- 0.

Sum Value at each HORIZONTAL LEVEL 4:- 30

Sum Value at each HORIZONTAL LEVEL 5:- 0

Sum Value at each HORIZONTAL LEVEL 6:- 0

Sum Value at each HORIZONTAL LEVEL 7:- 50

 

Above is the output for the problem; we have to see at every level if no child is present for any of the roots, then sum the particular root element for our answer.

Approach for Solving

Some steps below that give us more clarity in understanding the way to a solution for the problem are as follow:-

  1. Firstly, we are seeing it as if we have a Binary Tree, and we have to find the sum of leaf nodes horizontally for each level.
  2. Secondly, For horizontally finding the sum, directly incident the hints to visit the Binary Tree in the level order wise.
  3. Thirdly, if we visit the particular root, if we find there is no left and right element, then that root element with its level number is pushed in the map for the accumulated sum of leaf nodes at a horizontal level.
  4. Fourthly, if the root element has left the child, we move to the next level by pushing the nodes and level number to Node_with_level containing nodes with the level number at which node is present.
  5. Fifth, if the root element has the right child, then we have to move in a similar way to the left child in step-4 follow.
  6. At last, we iterate over the map we have created and find the sum accumulated for each of the levels for the leaf node horizontally.

 

These above all, the 6 steps help to solve the problem.

Code

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class BinaryTree {
  // We have created a Node Class for which it store the data , left and right child information of node
  static class Node{
      int data;
      Node left,right;
      Node(int data){
          this.data=data;
          left=right=null;
      }
  }
  // Node_with_level class holds the information of node with its respective level number.
  static class Node_with_level{
      Node node;
      int level;
      Node_with_level(Node node,int level){
          this.node=node;
          this.level=level;
      }
  }

  // We are printing the sum of the leaf node at every horizontal level
  static void print_horizontal_level_sum(Node root){
      if(root==null){
          System.out.println("No node is present , please enter the data!");
          return;
      }
      //map to store the sum at each leaf node at each horizontal level from start to end
      HashMap<Integer,Integer> mp=new HashMap<>();

      //Queue to hold the node with its level value
      Queue<Node_with_level> q=new LinkedList<Node_with_level>();
      // Firstly insert the root node with level number 1
      q.add(new Node_with_level(root,1));

      //Created a node which used for traversing the Tree
      Node_with_level nd_level;

      // Using the Level order manner we traversing the Binary Tree
      while(!q.isEmpty()){
          nd_level=q.peek();
          q.remove();

          // Creating a key for each of the level present in the Binary Tree
          if(!mp.containsKey(nd_level.level)){
              mp.put(nd_level.level,0);
          }

          // If the current node, at particular level is a leaf node
          if(nd_level.node.left==null && nd_level.node.right==null){
              // If we found the leaf node , then we map with the level to the sum of the leaf node
              // present at the level in horizontal manner
              mp.put(nd_level.level,mp.get(nd_level.level)+nd_level.node.data);
          }

          // If we have a left child then the present root is not a leaf so we move to the next level in the left direction.
          if(nd_level.node.left!=null){
              q.add(new Node_with_level(nd_level.node.left,nd_level.level+1));
          }

          //If we have a right child then the present root is noy leaf node , so we move to the next level in the right direction.
          if(nd_level.node.right!=null){
              q.add(new Node_with_level(nd_level.node.right,nd_level.level+1));
          }
      }
      int LEVEL=1;
      // Now Traverse the Map we have declared then find the value of the sum present at each level.
      for(Map.Entry e:mp.entrySet()){
          System.out.println("Sum Value at each HORIZONTAL LEVEL"+LEVEL+":- "+e.getValue()+".");
          LEVEL++;
      }
  }
  public static void main(String[] args){
      Node root=new Node(5);
      root.left=new Node(2);
      root.right=new Node(7);
      root.left.left=new Node(1);
      root.left.right=new Node(3);
      root.left.right.right=new Node(4);
      System.out.println("Sum of all the leaf node at every horizontal level");
      print_horizontal_level_sum(root);
  }

}

 

Dry-Run

 

To understand the problem, let’s take an example and have a dry run for the code.

 

Above is the Binary Tree we have taken for the Dry-Run:-

 

  1. First, we make a Node class to have linkage for the nodes, such that all the nodes get connected for which we form Binary Tree, having a constructor Node in the class with data, left and right nodes for left and right initially assigned with null.
  2. Second, we make a pair of things, like the Node_with_level function in which we have to make a constructor that stores the value of a node with a level number, which shows us which node is present at which level number.
  3. Third, we have to make print_horizontal_level_sum which does our task for printing the sum of Leaf Nodes at each Horizontal level of the Binary Tree.

 

Now we go through the implementation part for print_horizontal_level_sum:-

 

  1. First, we check the base condition root==null, here root ==5 so we move to the next step if it’s null, then we return from here itself.
  2. Second, if we find that we have an element, then we have to make a map, which stores the two integer values one is of level number and respective leaf node sum according to the given level number.
  3. Third, we have also stored the node and level number and created separate classes.
  4. As we get root==5, so we quenched the value 5 in the Queue, with level=1.
  5. Now we apply level order traversal one by one till we have elements in the Queue; we also have a key pair between the level number and sum of the leaf node.
  6. Initially, for the first-time visit, for the level number, all are assigned with the value of 0.
  7. Then we see 5 nodes have left ==null and right==null not there; it has left child also, then we move to level one up from 1 to 1+1=2. We have root==2 here, which we add in node with a level number, and we also see 5 also have a right child then we have again move one level up 1+1=2, then we have root==7 here which we add in node with a level number using a queue, now in the Queue we have to element 2 and 7, the loop continues.
  8. Now for 2, we have left and right child, so it’s not a leaf node, then we quenched the value 1 and 3 in the Queue, with status now looking 7 1 3 in the Queue.
  9. Now for 7, we have no left and right child; for that, we have to call the level number to insert in the map, previous stats sum calculated with the current stats node data, i.e. 0+7=7 for the level 2.
  10. Similarly, for 1, we see no left and right, do the same in step-9, we find the level 3 sum value is 1.
  11. For 3, we have a no left, but we have a right child; when we quenched 4, with level number and node, then we further move ahead with 4, then we find it has no left and right child and value of the sum at level 4 are 4

 

Complexity

Time Complexity for Sum of the leaf node at each Horizontal Level we are just iterating over the nodes present in the Tree and having stats of level number stored at the same time for each node, and we are accumulating the sum of leaf node by iterating over the nodes in O(N) where N is nodes and printing the sum of the leaf node in O(H) where H is the total level or height of the Tree as for each level we store the sum in the HashMap.

So overall, Time Complexity is O(N+H) ~ 2*O(N)~ O(N) when N==H.

 

Space Complexity is similar, as we are creating an Extra Node with a level number class which may contain elements singly at each level in the worst case, which is O(N) where N is no of nodes. We have also created a map extra for creating a key-pair between the level number and sum of leaf node at horizontal space at that level, which require O(H) where H is the height, so extra space is O(N+H) ~ 2*O(N)~ O(N) when N==H.

 

Hence Time Complexity is O(N), and Space Complexity is O(N).

Frequently Asked Question

1). What is a Binary Tree?

Ans: Tree having two children.

2). What is the leaf node of the Tree?

Ans: Nodes having no child.

3). What is a Tree?

Ans: Non-Linear data structure having no closed boundary.

4). What is Time and Space Complexity?

Ans: Time and Space Complexity both are O(N).

Key TakeAway

In this blog, we understand the concept of the Binary Tree and its application. We also learn about the level order traversing the Tree with the concept of the leaf node. We also understand the definition of a Binary Tree and learn the concept of non-linear data structure, how we create a Binary Tree. Using all the above concepts of Tree, Binary Tree, and leaf Node, tree traversal, we have solved the problem sum of all the leaf nodes at each horizontal level, in Time Complexity of O(N) and Space Complexity of O(N).  

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think