L3 · FAANGTrees~12 min · 4 tests

Binary Tree Level-Order Traversal

Return a binary tree's values level by level with BFS and a queue in O(n), using the queue length to separate levels. Includes the tree builder used in tests.

The problem

Return the values of the binary tree level by level, left to right: a list of lists.

The test builds trees with build_tree([3, 9, 20, None, None, 15, 7]) (level order, None = missing child). TreeNode has val, left, right.

Examples

Example 1

Input

level_order(build_tree([3, 9, 20, None, None, 15, 7]))

Expected output

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

Example 2
Input
```
level_order(build_tree([1]))
```
Expected output
```
[[1]]
```

+ 2 hidden tests on Submit — left-leaning chain.

Edge cases to ask about

Empty tree
Skewed tree

How the tests call your code

These helpers run before your code. The test inputs above call them.

from collections import deque as _deque


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


def build_tree(values):
    """Level-order list -> tree. None marks a missing child: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue, i = _deque([root]), 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i]); queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i]); queue.append(node.right)
        i += 1
    return root


def tree_values(root):
    """Tree -> level-order list with trailing Nones trimmed (the inverse of build_tree)."""
    out, queue = [], _deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.val)
        queue.append(node.left)
        queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · level_order

def level_order(root):
    """Values level by level: [[root], [children], ...]."""
    # Write your solution here
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
BFS, one level per loop	O(n)	O(w)	w = maximum width of the tree.
bestDFS carrying the depth	O(n)	O(h)	Append to out[depth].

Walkthrough of the optimal approach (try it yourself first)

BFS with a deque. The trick is snapshotting len(queue) at the start of each round: exactly that many nodes belong to the current level; their children form the next one.

DFS works too: pass the depth down and append to out[depth].

Complexity: O(n) time, O(n) space. Every node is enqueued and dequeued once; the queue can hold a whole level (up to n/2 nodes).

Reveal the reference solution

from collections import deque

def level_order(root):
    if root is None:
        return []
    out, queue = [], deque([root])
    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)
        out.append(level)
    return out

Follow-ups interviewers ask

Zigzag order.
Right side view (last value of each level).

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Binary Tree Level-Order Traversal in Python?

The optimal solution runs in O(n) time and O(n) auxiliary space. Every node is enqueued and dequeued once; the queue can hold a whole level (up to n/2 nodes).

What is the brute-force approach, and how do you optimise it?

BFS, one level per loop: O(n) time, O(w) space. w = maximum width of the tree. DFS carrying the depth: O(n) time, O(h) space. Append to out[depth].

What follow-up questions do interviewers ask about Binary Tree Level-Order Traversal?

Zigzag order. Right side view (last value of each level).