102. Binary Tree Level Order Traversal

Time: O(n)

Space: O(n)

Intuition

BFS naturally visits nodes level by level. The key trick to group nodes by level: at the start of each BFS iteration, snapshot the current queue size. That size is exactly how many nodes belong to the current level. Process exactly that many nodes before moving to the next level.

Algorithm

1If root is null, return empty list.
2Enqueue root. While the queue is not empty:
3Snapshot levelSize = queue.Count.
4Dequeue exactly levelSize nodes, add their values to a level list, enqueue their non-null children.
5Add the completed level list to the result.

Example Walkthrough

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

1.Queue: [3]. levelSize=1. Dequeue 3 -> level=[3]. Enqueue 9,20. Result=[[3]].
2.Queue: [9,20]. levelSize=2. Dequeue 9 -> enqueue nothing. Dequeue 20 -> enqueue 15,7. Result=[[3],[9,20]].
3.Queue: [15,7]. levelSize=2. Dequeue both -> level=[15,7]. Result=[[3],[9,20],[15,7]].

Output: [[3],[9,20],[15,7]]

Common Pitfalls

•Snapshot queue.Count BEFORE the inner loop - dequeuing nodes during the loop changes the count.
•Add both left and right children only if non-null to avoid null entries in the queue.

102.cs

// Approach: BFS with a queue to process nodes level by level.
// At the start of each iteration, snapshot the queue size — this is the exact count of nodes at the current level.
// Dequeue that many nodes, collect their values into a row list, and enqueue their non-null children.
// Append the completed row to the result after all nodes at that level are processed.
// Time: O(n) Space: O(n)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public IList<IList<int>> LevelOrder(TreeNode root)
    {
        IList<IList<int>> result = new List<IList<int>>();
        if (root == null)
            return result;
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);

        while (q.Count > 0)
        {
            int levelNum = q.Count;
            List<int> subList = new();
            for (int i = 0; i < levelNum; i++)
            {
                if (q.Peek().left != null)
                    q.Enqueue(q.Peek().left);

                if (q.Peek().right != null)
                    q.Enqueue(q.Peek().right);

                subList.Add(q.Dequeue().val);
            }
            result.Add(subList);
        }

        return result;
    }
}

Was this solution helpful?