Problem

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

Examples

Example 1:

graph TD;
    3 --> 9 & 20
    20 --> 15 & 7;
  
1
2

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

Example 2:

1
2

Input: root = [7, 1, 9, 0, 3, 8, 10, null, null, 2, 5, null, null, 4, 6]
Output: [7, 1, 9, 0, 3, 8, 10, 2, 5, 4, 6]

graph TD;

    7 --> 1 & 9
    1 --> 0 & 3
    9 --> 8 & 10
    3 --> 2 & 5
    5 --> 4 & 6

Variants

There are multiple variants possible for Level Order Traversal.

Solution

Method 1 - Iterative BFS Using Queue 🏆

Here is the approach:

  1. Start with an empty queue.
  2. Add one node, the root of the tree, to the queue.
  3. Loop until the queue is empty:
    • Dequeue a node.
    • Print its value.
    • Add its left and right children if they exist.

Pseudocode

1
2
3
4
5
6
7
8

Q.add(root)
while Q is NOT EMPTY
  T <- Q.remove
  print T.data
  if T.left
     Q.add(T.left)
  if T.right
     Q.add(T.right)

Hence the running time would be O(N).

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
	public List<Integer> levelOrder(TreeNode root) {  
	    Queue<TreeNode> queue = new LinkedList<>();
	    queue.add(root);
	    
	    List<Integer> ans = new LinkedList<>();
	    
	    while (!queue.isEmpty()) {
	        TreeNode curr = queue.poll();
	        ans.add(curr.val);
	        
	        if (curr.left != null) {
	            queue.add(curr.left);
	        }
	        
	        if (curr.right != null) {
	            queue.add(curr.right);
	        }
	    }
	    return ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[int]:
        queue = deque([root])
        ans = []
        
        while queue:
            node = queue[0]
            if node is not None:
                ans.append(node.val)
                queue.popleft()
                
                if node.left is not None:
                    queue.append(node.left)
                
                if node.right is not None:
                    queue.append(node.right)
                    
        return ans

Method 2 - Using 2 Stacks

Here is the logic:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

S1, S2 ;
S1.push(root)
while S1 OR S2 is not empty
   while S1 is not empty
       T <- S1.pop
       if T.left  
          print T.left.data
          S2.push(T.left)
       if T.right
          print T.right.data
          S2.push(T.right)
  while S2 is not empty
     S1.push(S2.pop)

Complexity

The level order traversal algorithm using two stacks exhibits a time complexity dependent on the tree’s height, particularly in skewed cases.

  • Nested Loops: The algorithm employs two nested loops. The outer loop iterates for O(H) times, where H represents the tree’s height. This loop ensures each level is visited.
  • Inner Loop and Level Iteration: Within each outer loop iteration, an inner loop processes the nodes in the current level. This inner loop’s execution time scales with the number of nodes in that level. In a balanced tree, the number of nodes at each level roughly doubles compared to the previous level, leading to an exponential growth of O(2^K) for the inner loop, where K represents the current level.

Combined Complexity:

Combining the outer and inner loops’ contributions, the initial expression for runtime becomes O(H) * O(2^K) + O(2^K). However, the constant term O(2^K) within the first summation can be ignored as it grows slower than the exponential term. Simplifying further, we get O(2^K) * (O(H) + 1), which essentially translates to O(H) * O(2^K).