Level Order Traversal Bottom Up: One Reverse Away

If you interview at Amazon, Microsoft, Adobe, expect some version of "Binary Tree Level Order Traversal II". It is rated Medium, and it falls squarely into the Tree BFS pattern — pattern-first preparation beats grinding random problems every time. Part 2 of 11 in the Tree BFS arc.

The Problem

Return the level order traversal from leaf level up to the root — deepest level first. A test of composure more than technique: the right answer is the standard traversal plus one reversal, and attempts to be cleverer usually make it worse.

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

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Output order changed; traversal order did not. When a problem tweaks only the presentation of a known traversal, transform the output — do not contort the algorithm. Recognizing which side of that line a variation falls on is a real skill.

The Approach

Run the exact level-order template, then return result[::-1] (or list(reversed(result))). Alternatively appendleft each level into a deque as you go — same complexity, marginally less readable.

If asked to avoid the reversal: compute depth first, pre-allocate the list of lists, and index by depth-from-bottom. Three options, one sentence each — then write the simple one.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque


def level_order_bottom(root: TreeNode | None) -> list[list[int]]:
    """Level lists ordered deepest first."""
    if not root:
        return []
    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])
    while queue:
        level: list[int] = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result[::-1]

Complexity

• Time: O(n) — standard BFS plus an O(L) reversal over L levels
• Space: O(w) — queue width, same as the template

Interview Tips and Follow-Ups

• Within-level order stays left to right — only the levels reverse. Misreading that spec is the actual failure mode here.
• If the interviewer pushes on the 'wasted' reversal, quantify it: O(L) list moves against O(n) traversal — noise. Numbers end debates.
• Bank the meta-lesson: presentation-only variants get output transforms, not algorithm rewrites.

That wraps part 2 of the Tree BFS arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.