Tree level order: keep the next frontier separate

Define a tree before choosing a traversal

A binary tree has at most two ordered children per node, one parent per nonroot node, and no cycles. Depth counts edges from the root. Node identity determines whether a node repeats; equal values do not. A simple baseline first finds tree height, then walks from the root separately for each depth. It revisits upper nodes and can take O(nh) time, including O(n²) on a chain of height n. Retaining the next frontier avoids those repeated walks.

Use a first-in, first-out queue, which removes the oldest enqueued node. At the start of an outer iteration, the queue contains exactly one level in left-to-right order. Snapshot its current length and pop exactly that many nodes, appending their values to the current output list and enqueueing left then right children. New children remain queued for the next iteration; looping until the queue is empty inside a level would mix every depth together.

Every node is enqueued once, and every child is one edge deeper than its parent, so the invariant advances to the next level. The reference uses deque.popleft; removing index zero from a Python list repeatedly shifts its remaining elements. It also records node identities when enqueuing and rejects repeats, covering both cycles and shared-child DAGs. Total time is O(n). The BFS frontier costs O(w), where w is maximum level width (the queue may contain parts of two levels, still O(w)); structural validation adds O(n) auxiliary identity storage. Returned values and nested lists cost O(n) output. For a guaranteed valid tree, omitting the seen set recovers O(w) auxiliary space but weakens the checked contract.

Follow-up 1: return zigzag levels

Predict which ordering must change. Keep traversal order ordinary so child discovery remains simple; reverse the values of every odd-numbered output level.

Do not reverse child enqueue order opportunistically: it changes later frontiers and is harder to prove. Reversing complete level lists adds O(n) total work.

Follow-up 2: the input becomes a DAG

The original API rejects this shape. A changed contract could emit each identity once at its shortest distance from root, marking visited on enqueue; BFS still establishes shortest unweighted distance. Alternatively, displaying every path can duplicate c and may have exponentially many entries. Explicit cycle policy is then necessary. A senior candidate names frontier and identity invariants and handles a deep chain iteratively. A lead candidate chooses whether the UI shows unique entities or containment paths and budgets output size accordingly.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/17-tree-level-order
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

from dataclasses import dataclass

@dataclass(eq=False)
class Node:
    value: object
    left: "Node | None" = None
    right: "Node | None" = None

from collections import deque

def tree_level_order(root):
    if root is None:
        return []
    if not isinstance(root, Node):
        raise ValueError("root must be Node or None")
    queue = deque([root])
    visited_nodes = {root}
    result = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            for child in (node.left, node.right):
                if child is None:
                    continue
                if not isinstance(child, Node) or child in visited_nodes:
                    raise ValueError("expected a tree without malformed or repeated nodes")
                visited_nodes.add(child)
                queue.append(child)
        result.append(level)
    return result

import random
import unittest
from solution import Node, tree_level_order

class LevelTests(unittest.TestCase):
    def test_examples_depth_and_identity(self):
        root = Node("a", Node("b", right=Node("d")), Node("c"))
        self.assertEqual(tree_level_order(root), [["a"], ["b", "c"], ["d"]])
        self.assertEqual(tree_level_order(Node(0, Node("x"), Node("x"))), [[0], ["x", "x"]])
        self.assertEqual(tree_level_order(None), [])
        deep = None
        for i in reversed(range(3000)):
            deep = Node(i, right=deep)
        self.assertEqual(tree_level_order(deep), [[i] for i in range(3000)])

    def test_reject_graphs_and_malformed_links(self):
        child = Node(1)
        for root in [42, Node(0, left=42), Node(0, child, child)]:
            with self.assertRaises(ValueError):
                tree_level_order(root)
        root = Node(0)
        root.left = root
        with self.assertRaises(ValueError):
            tree_level_order(root)
        self.assertIs(root.left, root)

    def test_dfs_depth_oracle(self):
        rng = random.Random(117)
        def build(depth):
            if depth == 0 or rng.random() < .25:
                return None
            return Node(rng.randrange(4), build(depth - 1), build(depth - 1))
        def visit(node, depth, levels):
            if node is None:
                return
            if depth == len(levels):
                levels.append([])
            levels[depth].append(node.value)
            visit(node.left, depth + 1, levels)
            visit(node.right, depth + 1, levels)
        for _ in range(200):
            root = build(6)
            expected = []
            visit(root, 0, expected)
            self.assertEqual(tree_level_order(root), expected)

if __name__ == "__main__":
    unittest.main()