Level Order Traversal of a Binary Tree

Given the root of a binary tree , return the level order traversal of the binary tree .

Level order traversal means picking nodes from left to right level by level.

For example,

For the below tree:

source: leetcode.com

Level order traversal is [[3],[9,20],[15,7]]

It is a list of lists.

Each list represent the nodes at that level from left to right.

At level 0 we have only one node 3 .

At level 1 we have two nodes 9 and 20 from left to right.

At level 2 we have two nodes 15 and 7 from left to right.

Try out the solution here:

https://leetcode.com/problems/binary-tree-level-order-traversal/

Solution:

Use DFS or BFS

Approach 1 – Use Depth First Search

In Depth First Search , as usual you use recursion.

Make recursive calls for both the left node and right of each node at each level.

Every recursive call should have a base condition.

In this case the base condition is checking if the node is null or not.

If it is null return .

Else start the main logic.

Have a global list named output to hold the list of nodes at each level.

Have a global variable named level to keep track of each level in the recursive call.

In the recursive call , you check the current level.

If it is equal to the output size , then the list of nodes for the current level is not already in the output list.

So create a new list of nodes and add it to the current level.

If it is not equal to output size , then that level is already in the output list , so add the current node to that list.

Below is the logic to populate the output list data structure:

      List<Integer> nodes = new ArrayList<>();
        
        
        nodes.add(node.val);
        
   
        
        if(output.size() == level ){
            
            
            output.add(nodes);
        }else{
            
            
            output.get(level).add(node.val);
        }

After the above step increment the level and make recursive calls on the left and right nodes of the current node.

Here is the logic:

int newlevel = level +1;
        traverse(node.left,newlevel);
        
        traverse(node.right,newlevel);

Here is the entire code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
     List<List<Integer>> output = new ArrayList<>();
    
    public List<List<Integer>> levelOrder(TreeNode root) {
    
   
        
         traverse(root,0);
        
        return output;
    }
    
    public void traverse(TreeNode node,int level){
        
        if(node == null) return;
        
        List<Integer> nodes = new ArrayList<>();
        
        
        nodes.add(node.val);
        
   
        
        if(output.size() == level ){
            
            
            output.add(nodes);
        }else{
            
            
            output.get(level).add(node.val);
        }
        
        int newlevel = level +1;
        traverse(node.left,newlevel);
        
        traverse(node.right,newlevel);
        
        
        return ;
        
        
    }
}

Algorithm:

  1. Create two global variables : one to hold the output and one to track the current level of the tree while doing DFS
  2. Invoke a recursive function with the initial level 0 and the root node.
  3. In the recursive function do the following:
  4. If the node is null , return – this is the base condition.
  5. If it is not null , then find if the current level is already in the output list
  6. If it is not already present (output size == level) , then create a new list , add the current node value and add this list to the output list
  7. If it is already present , then add the current node value to the output list for the specific level
  8. Increment the level.
  9. Invoke the recursive call for the left node
  10. Invoke the recursive call for the right node
  11. After the recursive function , return the output.

Time complexity:

Since we traverse each node once time complexity is O(n)

Space complexity:

There is a recursive call made for each node , so size of recursion stack is O(n)

Approach 2 – Breadth First Search

In this case , as usual we use a queue.

Add the first node to the queue.

Then until the queue is empty do the following:

  • Pop all elements in the queue and add it to the current level if it is already in the output list , else create a new list and add it to the output list
  • Put the left node and the right node of each element in the current level to the queue
  • Increment the level after processing all the elements in the current level.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
     
    
    public List<List<Integer>> levelOrder(TreeNode root) {
    
        List<List<Integer>> output = new ArrayList<>();
          
   
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        
        queue.add(root);
        
        int level = 0;
        
        while(!queue.isEmpty()){
            
            
            
            int size = queue.size();
            
            for(int i=0;i<size;i++){
                
                    
                TreeNode node = queue.poll();  
                
                
                if(node == null) continue;
                
                if(output.size() == level){
                    
                    List<Integer> nodes = new ArrayList<Integer>();            
                   
                    nodes.add(node.val);
                    
                    output.add(nodes);
                    
                    
                }else{
                    
                    
                    output.get(level).add(node.val);
                }
          
                queue.add(node.left);
                
                queue.add(node.right);
            }
          
           level++;
            
        }
        
      
        return output;
        
    }
}

Note that at the end of every iteration of the while loop ,

We will have all the nodes of the next level of the tree in the queue.

Algorithm:

  1. Create an output list to hold the list of node values at each level of the tree
  2. Create a queue to do BFS
  3. Put the root node into the queue
  4. While queue is not empty do the following:
  5. Check queue size and then for each node in the queue do the following:
  6. Pop the node
  7. If it is null , then check the next node
  8. Check if the current level is present in the output list , if no create a new one , else add the current node to the current level
  9. Put the left node of the current node into the queue
  10. Put the right node of the current node into the queue
  11. After all the nodes of the current level are processed , increment the level
  12. After all the nodes in the queue are processed return the output.

Time complexity:

Since we traverse each node once , time complexity is O(n)

Space complexity:

Each node is put into the queue so we need a queue of space O(n)

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s