Problem

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

NOTE : This problem is very similar to - Create linked lists of all the nodes at each depth for a Binary Tree

Examples

Example 1:

   3
  / \
 9   20
    /  \
   15   7

Input: root = [3,9,20,null,null,15,7]
Output: [ [3], [9, 20], [15, 7] ]

Solution

Method 1 - Naive Approach

Here is the logic:

  • Get the height of the tree.
  • Put a for loop for each level in tree.
  • for each level in step 2, do pre order traversal and print only when height matches to the level.

Look at the code for better explanation

public void levelOrder(TreeNode root) {
    int h = height(root);
    List<List<Integer>> ans = new LinkedList<>();
    for (int i = 1; i <= h; i++) {
	    List<Integer> currLevel = new LinkedList<>();
        printLevels(root, i, currLevel);
        ans.add(currLevel);
    }
    return ans;
}

public void printLevels(TreeNode root, int h, List<Integer> currLevel) {
    if (root == null) {
	    return;
	}
    if (h == 1) {
	    currLevel.add(root.val);
	}
    else {
        printLevels(root.left, h - 1, currLevel);
        printLevels(root.right, h - 1, currLevel);
    }
}

public int height(Node root) {
    if (root == null) {
	    return 0;
	}
    return 1 + Math.max(height(root.left), height(root.right));
}

Complexity

  • Time Complexity : O(N^2) – because each level you are traversing the entire tree.

Method 2 - Using Queue and Size of Queue 🏆

  • Create a ArrayList of Linked List Nodes.
  • Do the level order traversal using queue(Breadth First Search) - Binary Tree Traversal - Level Order
  • For getting all the nodes at each level, before you take out a node from queue, store the size of the queue in a variable, say you call it as queueSize.
  • Now while queueSize>0, take out the nodes and print it and add their children into the queue.
  • After this while loop put a line break.

Dry Running of Above Code

Note, in the diagram we are calling levelNodes = queueSize. Since we had taken the queue size before we add new nodes, we will get the count at each level and after printing this count, put a line break, see the example below

Code

Java
public List<List<Integer>> levelOrder(TreeNode root) {
	List<List<Integer>> ans = new ArrayList<>();
	if (root == null) {
		return ans;
	}

	Queue<TreeNode> queue = new LinkedList<>();
	queue.offer(root);

	while (!queue.isEmpty()) {
		List<Integer> currentLevel = new ArrayList<>();
		int queueSize = queue.size();
		for (int i = 0; i < queueSize; i++) {
			TreeNode curr = queue.poll();
			if (curr.left != null) {
				queue.offer(curr.left);
			}
			if (curr.right != null) {
				queue.offer(curr.right);
			}

			currentLevel.add(curr.val);
		}

		ans.add(currentLevel);
	}

	return ans;
}

For more, Refer here.

Complexity

  • Time Complexity – O(n) where n is number of vertices as we go through all nodes
  • Space Complexity - O(n) for storing elements in queues

Method 3 - Using 2 Queues

It is obvious that this problem can be solve by using a queue. However, if we use one queue we can not track when each level starts. So we use two queues to track the current level and the next level.

Code

Java
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
   List<List<Integer>> ans = new ArrayList<ArrayList<Integer>>();
   
   if(root == null)
       return ans;

   List<Integer> nodeValues = new ArrayList<>();
   Queue<TreeNode> current = new LinkedList<>();
   Queue<TreeNode> next = new LinkedList<>();
   current.add(root);

   while(!current.isEmpty()){
       TreeNode node = current.poll();

       if(node.left != null) {
	       next.add(node.left);
       }
       
       if(node.right != null) {
	       next.add(node.right);
       }
       
       nodeValues.add(node.val);
       if(current.isEmpty()){
           current = next;
           next = new LinkedList<TreeNode>();
           ans.add(nodeValues);
           nodeValues = new ArrayList();
       }

   }
   return ans;
}

Complexity

  • Time Complexity – O(n) where n is number of vertices as we go through all nodes
  • Space Complexity - O(n) for storing elements in queues

Method 4 - DFS Recursive Approach

I think that the recursive way of traversal is truly not recursive, it eventually relies on iterative steps over the height of the tree and the recursion can only be used in identifying the correct level and printing it.

Code:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) {
	        return levels;
	    }
        helper(root, levels, 0);
        return levels;
    }
    
    public void helper(TreeNode root, List<List<Integer>> ans, int level) {
        if (root == null) {
	        return;
	    }
        if (res.size() < level + 1) {
            ans.add(new ArrayList<>());
        }
        ans.get(level).add(root.val);
        helper(root.left, ans, level + 1);
        helper(root.right, ans, level + 1);
    }
}

As we can see the for loop runs for O(H) time where H is the height of the tree. Each of these H calls to the printCurrentLevel routine takes O(H) * O(2K) time as in the previous iterative way and the same justification holds true for this algorithm as well.

Summary

This problem opens many possibilities to work with. For eg.

  1. Populate next pointer to right node in Binary Tree
  2. Find level of a node, etc.