Approach for Solving
Some steps below that give us more clarity in understanding the way to a solution for the problem are as follow:
 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.
 Secondly, For horizontally finding the sum, directly incident the hints to visit the Binary Tree in the level order wise.

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.
 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.
 Fifth, if the root element has the right child, then we have to move in a similar way to the left child in step4 follow.
 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);
}
}
DryRun
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 DryRun:
 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.
 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.
 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:
 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.
 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 the respective leaf node sum according to the given level number.
 Third, we have also stored the node and level number and created separate classes.

As we get root==5, so we quenched the value 5 in the Queue, with level=1.

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 the sum of the leaf node.
 Initially, for the firsttime visit, for the level number, all are assigned with the value of 0.
 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.
 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 the status now looking 7 1 3 in the Queue.
 Now for 7, we have no left and right child; for that, we have to call the level number to insert in the map, the previous stats sum calculated with the current stats node data, i.e. 0+7=7 for level 2.
 Similarly, for 1, we see no left and right, do the same in step 9, and we find the level 3 sum value is 1.
 For 3, we have 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 keypair 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 Questions
What is a Binary Tree?
The tree has two children.
What is the leaf node of the Tree?
Nodes having no child.
What is a Tree?
NonLinear data structure having no closed boundary.
What is Time and Space Complexity?
Time and Space Complexity both are O(N).
Conclusion
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 nonlinear data structure, and 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).
Recommended Problems:
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Cheers!