Bottom-Up Level Order Traversal

Interview Problem Interview Medium Binary Tree Queue Breadth-first Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.levelOrderBottom(root). Return tree levels from bottom to top, keeping left-to-right order within each level.

Starter code

class Solution:
    def levelOrderBottom(self, root):
        pass

Test cases

sample

{
  "args": [
    {
      "$type": "binary-tree",
      "values": [
        3,
        9,
        20,
        null,
        null,
        15,
        7
      ]
    }
  ]
}

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

Wizard outline

Step 1: Initialize Solution.levelOrderBottom
Replace the empty starter with the first real state owned by Solution.levelOrderBottom. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the One case
Complete the readable core algorithm for one representative Interview case. Perform standard BFS then reverse the level list, not the values inside levels.
Step 4: Harden the Sample boundary
Repair the reviewed boundary and pass the complete submission contract. BFS produces every depth in increasing order with correct within-level ordering. Reversing only the outer list produces decreasing depth while preserving each level exactly.

Footguns and prerequisites

Bottom-up changes only level order; node order within every level stays left-to-right.
trees and graphs

Reviewed references

LeetCode 107 — Binary Tree Level Order Traversal II

Practice prerequisites

Expand One Tree Level(opens in a new tab)
Expand One Tree Level isolates at the start of each outer iteration, the queue contains exactly the current level in left-to-right order. That focused state discipline is required when implementing bottom up level order as a complete Interview Problem.

Recommended approach and implementation

Run ordinary left-to-right BFS by fixed level sizes, append each level, then reverse the outer result.

Why it works: BFS produces every depth in increasing order with correct within-level ordering. Reversing only the outer list produces decreasing depth while preserving each level exactly.

class Solution:
    def levelOrderBottom(self, root):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if root is None: return []
        from collections import deque
        queue = deque([root])
        levels = []
        while queue:
            level = []
            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)
            levels.append(level)
        return levels[::-1]

Similar exercises

Binary Tree Level Order(opens in a new tab)