Skip to content

083 — Binary Tree Level Order Traversal

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

83 — Binary Tree Level Order Traversal

LeetCode 102 · Medium. Given the root of a binary tree, return the values of its nodes as a list of lists, one inner list per level, from top to bottom, left to right.

🍽️ Intuition

Think about reading an org chart out loud one rank at a time: "here's the CEO; here are all the VPs; here are all the directors reporting to those VPs; ..." You never announce someone before everyone above their rank has been announced. That's exactly what level-order traversal is — visit the tree rank by rank, and within a rank, left to right.

🚩 Pattern-Recognition Cue

"Level by level" / "rank by rank" / "layer by layer" is about as direct a BFS cue as this wiki has — this problem is the canonical textbook example of BFS on a tree, no stretch required. A queue naturally processes nodes in the order they were discovered, and if you snapshot "how many nodes are currently in the queue" before processing each round, that snapshot is exactly one tree level.

🐢 Brute Force

Do a DFS that visits every node while tracking its depth, recording (value, depth) pairs into one flat array as it goes — extra bookkeeping — then, in a separate pass, group those pairs by depth to build the final level-by-level result.

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val }
}

func collectWithDepth(_ node: TreeNode?, _ depth: Int, _ pairs: inout [(value: Int, depth: Int)]) {
    guard let node = node else { return }
    pairs.append((node.val, depth))
    collectWithDepth(node.left, depth + 1, &pairs)
    collectWithDepth(node.right, depth + 1, &pairs)
}

func levelOrderBruteForce(_ root: TreeNode?) -> [[Int]] {
    var pairs: [(value: Int, depth: Int)] = []
    collectWithDepth(root, 0, &pairs)

    guard let maxDepth = pairs.map({ $0.depth }).max() else { return [] }

    var levels: [[Int]] = Array(repeating: [], count: maxDepth + 1)
    // NOTE: this DFS visits left-before-right at each node but doesn't guarantee
    // left-to-right ORDER WITHIN a level when appended out of traversal order in
    // general graphs — for a tree, preorder DFS does still emit each level's nodes
    // left-to-right, since it fully finishes a left subtree before starting the right one.
    for pair in pairs {
        levels[pair.depth].append(pair.value)
    }
    return levels
}

// smoke test: 3 -> (9, 20 -> (15, 7))
let bfRoot = TreeNode(3)
bfRoot.left = TreeNode(9)
bfRoot.right = TreeNode(20)
bfRoot.right?.left = TreeNode(15)
bfRoot.right?.right = TreeNode(7)
print(levelOrderBruteForce(bfRoot))   // [[3], [9, 20], [15, 7]]

Big-O: O(n) time — one DFS pass to collect pairs, one pass to group them. O(n) extra space for the flat (value, depth) array, on top of the O(n) result itself — the grouping step is pure overhead the BFS version below doesn't need.

🚀 Optimal

Walk the tree with a queue. Before processing each round, snapshot the queue's current size — that snapshot is exactly the number of nodes in the current level — then dequeue exactly that many nodes, building this level's array directly and enqueueing their children for the next round.

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }

    var result: [[Int]] = []
    var queue: [TreeNode] = [root]

    while !queue.isEmpty {
        let levelSize = queue.count   // snapshot: exactly how many nodes are in THIS level
        var level: [Int] = []

        for _ in 0..<levelSize {
            let node = queue.removeFirst()
            level.append(node.val)
            if let left = node.left { queue.append(left) }
            if let right = node.right { queue.append(right) }
        }

        result.append(level)
    }

    return result
}

// smoke test: same tree as above
let root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right?.left = TreeNode(15)
root.right?.right = TreeNode(7)
print(levelOrder(root))   // [[3], [9, 20], [15, 7]]

print(levelOrder(nil))   // [] — empty tree has no levels

// single node
print(levelOrder(TreeNode(1)))   // [[1]]

Big-O: O(n) time — every node is enqueued and dequeued exactly once. O(n) extra space for the queue and result (inherent to the problem — the output itself is every node grouped by level), but no separate grouping pass is needed: each level array is built directly, in the right order, in one linear walk.

🔑 The Key Insight

Both approaches are O(n) time and land at O(n) space overall — there's no asymptotic gap here. The real difference is tidiness: the brute force records depth information alongside every node and then has to reconstruct the level grouping afterward as a second, separate step. The queue-driven walk gets the grouping for free, because "snapshot the queue's current size before this round" is "here's exactly what belongs in this level" — no post-processing, no extra depth bookkeeping, no second pass.

🔗 Related Chapters

  • Binary Trees — the structure being traversed.
  • Queues & Deques — the queue that drives the level-by-level walk; each "round" of dequeuing corresponds to exactly one tree level.
  • BFS — this problem is the textbook example of the pattern: level-order traversal is BFS.

🧸 Memory Sentence

Level Order Traversal is reading the org chart rank by rank — snapshot how many people are in the current rank before you start announcing them, and that snapshot tells you exactly where one level ends and the next begins.

✅ Check Your Understanding

Trace the optimal algorithm on the tree 3 -> (9, 20 -> (15, 7)). At the start of each while loop iteration, write down the queue's contents and the levelSize snapshot taken for that round. Explain why snapshotting queue.count before the inner for loop begins is essential — what would go wrong if you checked queue.count fresh on every iteration of the inner loop instead?

⬅️ Previous: Lowest Common Ancestor of a Binary Search Tree · Next: Binary Tree Right Side View ➡️

Clone this wiki locally