Binary TreesProblem 1 of 35

Level order traversal

Brute Force
Time: O(n^2)
Space: O(n)
Optimal
Time: O(n)
Space: O(n)

Problem Statement

Given a binary tree, perform level order traversal (BFS) and return the nodes level by level from left to right.

Example:

1 / \ 2 3 / \ \ 4 5 6
  • Input: Root of the above tree
  • Output: [[1], [2, 3], [4, 5, 6]] or [1, 2, 3, 4, 5, 6]

Approach 1: Brute Force (Using Height)

Intuition

Calculate the height of the tree, then for each level from 1 to height, traverse the tree and print nodes at that level.

Algorithm

  1. Calculate the height of the tree
  2. For each level from 1 to height:
    • Traverse the tree recursively
    • Print nodes when the current level equals the target level
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
    
    public void printLevel(TreeNode root, int level, List<Integer> result) {
        if (root == null) return;
        if (level == 1) {
            result.add(root.val);
        } else {
            printLevel(root.left, level - 1, result);
            printLevel(root.right, level - 1, result);
        }
    }
    
    public List<Integer> levelOrderBruteForce(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        int height = getHeight(root);
        
        for (int i = 1; i <= height; i++) {
            printLevel(root, i, result);
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n^2) - For each level, we traverse the entire tree
  • Space Complexity: O(n) - Recursion stack in worst case (skewed tree)

Approach 2: Optimal (Using Queue - BFS)

Intuition

Use a queue to process nodes level by level. For each level, process all nodes currently in the queue and add their children for the next level.

Algorithm

  1. Initialize a queue with the root node
  2. While queue is not empty:
    • Get the current level size
    • Process all nodes at the current level
    • Add their children to the queue
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            result.add(currentLevel);
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each node is visited exactly once
  • Space Complexity: O(n) - Queue can hold at most n/2 nodes (last level of complete binary tree)

Key Takeaways

  1. BFS with Queue is the standard approach for level order traversal
  2. Track level size before processing to separate levels
  3. The brute force approach is useful when you can't use extra space for a queue
  4. Level order traversal is fundamental for many tree problems (zigzag, right view, etc.)
Next
Reverse Level Order traversal