Level order traversal

Time: O(n)

Space: O(n)

Intuition

BFS with level-size snapshotting: enqueue root, then for each level, dequeue exactly levelSize nodes and enqueue their children.

Algorithm

1Same as LeetCode 102: BFS with queue. Snapshot size at start of each level.

Example Walkthrough

Input: root = [1, [2,3], [4,5,6,7]]

1.Level 0: [1]. Level 1: [2,3]. Level 2: [4,5,6,7].

Output: [[1],[2,3],[4,5,6,7]]

Common Pitfalls

•Snapshot queue.size() BEFORE the inner dequeue loop.

Level order traversal.java

Java

// Approach: BFS with a queue. Process each level fully before moving to the next.
// Time: O(n) Space: O(n)
class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(Node root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (root == null)
            return list;
            
        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            int size = q.size();
            ArrayList<Integer> ll = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node curr = q.remove();
                ll.add(curr.data);
                if (curr.left != null)
                    q.add(curr.left);
                if (curr.right != null)
                    q.add(curr.right);
            }
            list.add(ll);
        }
        return list;
    }
}

Was this solution helpful?