Binary Tree Vertical Traversal: BFS Order, Coordinate Sorting, and Tie-Break Rules

Binary tree vertical traversal begins with an ordering contract. Give the root column zero and row zero; move left one column for a left child, right one for a right child, and down one row for either child. Then ask what happens when two nodes occupy the same row and column. Keeping their breadth-first, left-to-right order and sorting their values produce different valid answers to different specifications.

For the BFS-stable version, start with PracHub’s Group a tree by vertical columns. Its practice contract explicitly preserves level-order appearance on ties. The official LeetCode 987 definition instead sorts tied positions by value. Confirm the tie rule before choosing your data structure.

Evidence boundary: the official problem and Python documentation support the cited technical facts. The examples, implementations, proofs, and bounded checks below are original teaching work. PracHub records provide practice contracts, not predictions of an employer’s questions. No independent candidate reports or hiring-process claims are used.

Define the complete ordering key before traversing

A column groups nodes horizontally; a row records depth. These coordinates describe paths through the tree, not array positions or a drawing’s pixel spacing. For a path with two left edges and one right edge, the column is minus one and the row is three. Null children contribute no value and need no coordinate record.

There are three ordering levels. First, emit columns from smallest to largest. Second, emit nodes within each column from shallowest to deepest. Third, resolve nodes sharing both coordinates using the requested tie rule. The same-position tie rule is where otherwise identical questions produce different answers.

Do not silently infer the rule from “vertical traversal,” a company name, or a remembered problem number. The public LeetCode 314 description was Premium-locked when researched; this article grounds its BFS-stable alternative in the linked PracHub specifications rather than presenting an inaccessible official statement as freshly verified evidence.

Make the disagreement visible with five nodes

Build a root valued eight, with left child four and right child six. Four has only a right child, nine; six has only a left child, two. Both grandchildren land at column zero, row two. They are distinct nodes even though their coordinates coincide.

The center column starts with eight under either contract. Ordinary left-child-first BFS encounters nine before two, giving the complete result [[4], [8, 9, 2], [6]]. The value-sorted contract changes only the tied pair, giving [[4], [8, 2, 9], [6]].

This example is more diagnostic than a tree whose tied nodes already appear in ascending value order. A sample containing grandchildren two and nine in that order would let both implementations pass while hiding the distinction. Choose values that force the two tie rules to disagree, so one test can expose a missing comparison.

Changing two to nine gives two separate copies of the value nine in the output. Neither contract deduplicates nodes by value or coordinate. A set of values is therefore the wrong representation, even if the examples you initially tried happened to contain unique numbers.

Why left-child-first BFS supplies one contract automatically

A FIFO queue processes nodes by nondecreasing depth. Within a level, enqueueing each parent’s left child before its right child preserves left-to-right appearance. Appending each visited value to its column therefore already satisfies the BFS-stable contract; rows do not need to be stored explicitly.

Explain what the queue guarantees before relying on its order. After removing a node, all remaining nodes of its depth stay ahead of children just appended for the next depth. Inductively, parents appear left to right, and their children are appended in that same parent order. Filtering this traversal down to one column preserves the required relative order.

Python’s deque documentation describes efficient appends and pops at either end. Use popleft() for FIFO removal. Repeatedly removing the first element of a Python list shifts the remaining elements and can make a broad-tree traversal quadratic. A list with a monotonically advancing read index is another valid queue, but retains already processed references unless explicitly managed.

Changing child insertion to right before left changes ties. That is useful for some view problems, but it contradicts the BFS-stable contract used here. A queue alone is not the whole correctness argument; its insertion order matters too.

Implement both specifications without mutating the tree

The following complete Python implementation uses node objects with integer values. It assumes a valid finite binary tree: no cycles and no shared child object reached through multiple parents. Graph validation is a separate requirement. An empty root returns an empty result, and neither function changes node values or links.

The first function stores column lists and their minimum and maximum coordinates. The second records explicit triples and sorts them lexicographically, as described in the Python sorting guide. Its iterative DFS visits left before right, but that incidental traversal order does not determine the strict answer because sorting imposes the specification afterward.

from collections import defaultdict, deque
from dataclasses import dataclass

@dataclass(eq=False)
class Node:
    val: int
    left: 'Node | None' = None
    right: 'Node | None' = None

def vertical_bfs(root):
    if root is None:
        return []
    columns = defaultdict(list)
    queue = deque([(root, 0)])
    lo = hi = 0
    while queue:
        node, col = queue.popleft()
        columns[col].append(node.val)
        lo = min(lo, col)
        hi = max(hi, col)
        if node.left is not None:
            queue.append((node.left, col - 1))
        if node.right is not None:
            queue.append((node.right, col + 1))
    return [columns[c] for c in range(lo, hi + 1)]

def vertical_sorted(root):
    if root is None:
        return []
    records = []
    stack = [(root, 0, 0)]
    while stack:
        node, col, row = stack.pop()
        records.append((col, row, node.val))
        if node.right is not None:
            stack.append((node.right, col + 1, row + 1))
        if node.left is not None:
            stack.append((node.left, col - 1, row + 1))
    records.sort()
    out, previous = [], None
    for col, row, value in records:
        if col != previous:
            out.append([])
            previous = col
        out[-1].append(value)
    return out

Notice that sorting places the row before the value. Sorting only (column, value) would let a small descendant jump ahead of a larger ancestor. Conversely, sorting only column and row would leave equal-position values dependent on the original traversal, which is insufficient for the strict contract.

The previous column variable groups an already ordered sequence; it is not a visited set. Equal triples must still be appended separately. If records include node objects as an extra tuple field, avoid making Python compare those objects when all numeric keys tie. Sorting with an explicit numeric key avoids that accidental requirement.

DFS is valid when the missing order is restored

“DFS cannot solve vertical traversal” is too broad. DFS can collect every node with enough positional information, after which sorting supplies the desired order. The second implementation does exactly that. Plain preorder appends can put a row-four node before a row-two node in the same column; the extended example below shows that failure.

Extend the five-node example: give nine a left child three, then give three a right child seven. Seven returns to column zero at row four. Preorder enters the left subtree completely, so its center-column append order becomes eight, nine, seven, two. The shallower two appears too late.

BFS produces eight, nine, two, seven. Strict coordinate/value sorting produces eight, two, nine, seven. This separates two independent errors: wrong depth order and wrong same-position tie order. If a fix still fails the next sample, check depth order and same-position ties separately before rewriting the traversal.

For the BFS-stable contract, DFS can store each node’s row and a left-first discovery sequence, then sort by column, row, and sequence. At a fixed depth, left-first preorder preserves relative left-to-right order. A root-to-node path key also works, but copying long paths adds cost; the queue version obtains the necessary order more directly.

Account for columns, width, sorting, and output

Let n be the node count, c the number of occupied columns, and w the maximum width of a level. Under expected constant-time dictionary operations, the BFS implementation visits each node once and constructs the result in linear time. Its queue uses O(w) space, while the stored column values and returned output together require O(n) references.

Scanning from minimum to maximum column does not hide a huge empty numeric range. Every edge changes the column by exactly one. A path from the root to any extreme passes through all intermediate integer columns, so occupied columns form a contiguous range and c is at most n. This property belongs to these tree coordinates, not arbitrary dictionary keys.

Sorting just the column keys gives an alternative O(n + c log c) implementation. Global triple sorting, as shown for the strict version, has an O(n log n) upper bound and O(n) storage including records and output. Iterative traversal avoids recursive call-stack limits, although its explicit stack can still grow with tree height.

A level-by-level BFS that sorts only groups sharing row and column is also possible for the strict version. Its sorting work depends on collision-group sizes. Do not advertise plain O(n) time for unrestricted value sorting merely because discovery used BFS; comparison sorting still contributes work.

Validate the rule with an independent path oracle

Original checks ran under Python 3.12.14. The saved harness enumerated all ordered binary-tree shapes with zero through seven nodes and every assignment of values zero or one. Across 64,979 labeled trees, both implementations matched an independent oracle.

That oracle derives coordinates from complete root-to-node paths. It orders BFS-stable ties by path strings at equal depth and strict ties by value, rather than using the production queue or its column-extreme logic. Distinct construction and ordering mechanisms reduce the chance of checking one implementation against a copy of itself.

Additional named checks covered the nine/two disagreement, the deeper preorder collision, retention of equal values, and a 5,001-node right chain handled iteratively. The checks also demonstrate failures from sorting a column by value without depth and from appending DFS preorder without restoring depth order.

These are bounded structural checks, not performance benchmarks or proof for every possible integer/tree size. The complete implementations appear above; the exhaustive harness and machine-readable receipt are retained with the local article artifacts. In an interview, reproduce the small counterexamples first, then explain the invariant that generalizes beyond them.

Keep input encoding separate from traversal semantics

A level-order array is an encoding of a tree, not automatically a heap-indexed array. Some interfaces consume the next two child entries for each existing parent; others assign children to positions 2*i+1 and 2*i+2. Those conventions differ for sparse trees. Clarify the interface before building node objects.

The two linked vertical-order practice records use different presentations of the same ordering idea. Read their complete input contracts. Reusing a decoder from a neighboring task can construct a different tree even when the traversal itself is correct. A decoder error and a sorting error can produce equally plausible-looking wrong columns.

Likewise, a binary search tree’s value order does not replace coordinate order. Inorder traversal sorts BST values, whereas vertical traversal groups spatial positions. If the input permits repeated values, they remain separate nodes regardless of BST insertion conventions.

Practice five different ordering and representation checks

These are practice records, not evidence of a universal interview sequence. The related binary-tree serialization article develops reversible representation; it solves a different problem from output ordering.

When presenting your solution, state the complete ordering key, trace the colliding grandchildren, and name the operation that enforces each part of the contract. Then change only the tie rule and explain which code must change. Open Group a tree by vertical columns, implement its stated tie rule, and compare both outputs on the five-node tree before changing the specification.

Sources and Further Reading

• LeetCode 987: Vertical Order Traversal of a Binary Tree
• Python documentation: collections.deque
• Python sorting documentation: key functions and stability

Technical sources and linked practice contracts checked October 16, 2026. Original check results describe the saved Python 3.12.14 run only.