Binary Tree Vertical Order

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

Layout engines, file-tree visualizers, and spreadsheet apps all need to place nodes into vertical columns: every node gets an x-position derived from its ancestors, and ties within a column need a deterministic reading order. That is exactly vertical-order traversal.

The tree is given as a nested list [value, left, right]; an absent subtree is an empty list []. Values are distinct integers. The root sits in column 0, a left child is one column left of its parent (col - 1), and a right child is one column right (col + 1). Return the values grouped by column, ordered left to right.

For this tree:

     1
   /   \
  2     3
 / \     \
4   5     6

the columns are -2: [4], -1: [2], 0: [1, 5], 1: [3], 2: [6].

Level 1 - Column groups

Return the values grouped by column, columns ascending left to right. Within a single column the order is unspecified at this level, so the tests sort each group's contents before comparing.

tree = [1, [2, [4, [], []], [5, [], []]], [3, [], [6, [], []]]]
vertical_order(tree)  # [[4], [2], [1, 5], [3], [6]] - within-column order not yet checked

Level 2 - BFS row order

From here on, within-column order matters. With the default ties="bfs" a column reads top to bottom, and nodes on the same row read left to right - which is exactly the order a level-order (BFS) traversal discovers them. Watch out: two nodes can land in the same column at the same depth but be discovered in an order unrelated to their values.

The order of columns in the output stays left to right.

tree = [1, [2, [], [7, [], []]], [4, [-5, [], []], []]]
# 7 is 2's right child (col 0, depth 2); -5 is 4's left child (col 0, depth 2).
# BFS expands 2 before 4, so 7 is discovered first.
vertical_order(tree)  # [[2], [1, 7, -5], [4]]

Level 2 adds an optional tie-break parameter to the signature:

def vertical_order(tree: list, ties: str = "bfs") -> list[list[int]]: ...

Level 3 - DFS ties by value

Passing ties="value" switches to the depth-then-value reporting rule: within a column, shallower nodes always stack above deeper ones, and nodes sharing a depth in the same column sort ascending by value. Depth dominates - the value tie-break only fires between nodes at the same depth.

tree = [1, [2, [], [7, [], []]], [4, [-5, [], []], []]]
vertical_order(tree, ties="value")  # [[2], [1, -5, 7], [4]]

The same tree as Level 2, but the depth-2 tie in column 0 now reads -5 before 7 because -5 < 7, even though BFS discovers 7 first.

Level 4 - Adversarial shapes

Finally, shapes built to punish recursion: a left-skewed chain 10^4 levels deep, a single node, wide zigzags that spread one node per column, and deep+wide combinations. Build the inputs with loops, not recursive helpers, and make sure your traversal is iterative too - a recursive DFS at depth 10^4 in Python will hit the recursion limit before it sees the leaf.

Patterns used

Foundations primers this challenge draws on.

DFS

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed