List a tree's values row by row

Trees Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank so each round handles exactly one row.

Python 3.13
from collections import deque
level = [8, 3, 10, 1, 6, None, 14]
kids = {i: [j for j in (2 * i + 1, 2 * i + 2)
            if j < len(level) and level[j] is not None]
        for i in range(len(level))}
q = deque([0])
out = []
while q:
    row = []
    for _ in range(____):
        i = q.popleft()
        row.append(level[i])
        q.extend(kids[i])
    out.append(row)
print(out)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A len(q)

Right: the queue holds exactly the current row when the round starts.

Reading the queue length once, before children are added, separates the rows.

Why not the others?
  • B len(level). That tries to take every node in the first round.
  • C 2. Rows double at most; a fixed count breaks on uneven trees.
The tree 8, 3, 10, 1, 6, 14, 4, 7 visited row by row from the top.

Steps come from running the Python solution.

Text version

level order:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 8
  2. Visit 3
  3. Visit 10
  4. Visit 1
  5. Visit 6
  6. Visit 14
  7. Visit 4
  8. Visit 7

Result: [[8], [3, 10], [1, 6, 14], [4, 7]]. Order: 8, 3, 10, 1, 6, 14, 4, 7

preorder:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 8
  2. Visit 3
  3. Visit 1
  4. Visit 6
  5. Visit 4
  6. Visit 7
  7. Visit 10
  8. Visit 14

Result: [8, 3, 1, 6, 4, 7, 10, 14]. Order: 8, 3, 1, 6, 4, 7, 10, 14

30-second answer

Breadth-first search with a queue. At the start of each round the queue holds exactly one row; take that many nodes, record their values and queue their children. Each node is queued and removed once: O(n) time, O(w) extra space for the widest row w.

Practise saying it · 45 s. No recording, just a timer

Explain level-by-level BFS.

Say your answer out loud, then check which of these points you covered:

  • Queue
  • Fix the row size first
  • O(n) time, O(w) space

Deep dive

for _ in range(len(queue)) fixes the row size before children are added, which is what separates rows.

A recursive DFS that passes depth and appends into rows[depth] gives the same result.

Right-hand view, row averages and zigzag order are all small changes to this loop.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from collections import deque


def rows(root: Node | None) -> list[list[int]]:
    out: list[list[int]] = []
    queue = deque([root] if root else [])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.val)
            queue.extend(c for c in (node.left, node.right) if c)
        out.append(row)
    return out

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun rows(root: Node?): List<List<Int>> {
    val out = mutableListOf<List<Int>>()
    val queue = ArrayDeque<Node>()
    if (root != null) queue.addLast(root)
    while (queue.isNotEmpty()) {
        val row = mutableListOf<Int>()
        repeat(queue.size) {
            val node = queue.removeFirst()
            row.add(node.value)
            node.left?.let { queue.addLast(it) }
            node.right?.let { queue.addLast(it) }
        }
        out.add(row)
    }
    return out
}

Common mistakes

  • Using a list with pop(0), which makes the walk O(n²).
  • Reading len(queue) inside the loop after children were added.

Senior take & follow-ups

Name the 'fix the row size first' trick; it is the detail that makes the code correct.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you print zigzag rows?

    Show hint

    Reverse every other row, or append to the left of a deque on odd rows.

  2. What is the space cost on a complete tree?

    Show hint

    The last row holds about n/2 nodes, so O(n).

What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.