Binary Tree Vertical Order Traversal
Asked at Apple
Problem
Group the nodes of a binary tree by horizontal column, where the root sits at column 0, left children shift one column lower, and right children shift one column higher. Return the columns sorted left to right, each column ordered top to bottom - the Apple staple that combines BFS with a hash map.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
How to Think About It
Baseline: a recursive DFS carrying a column offset produces correct groups, but depth-first order cannot guarantee top-to-bottom ties are emitted in the right sequence, so you must sort everything - O(n log n) and messier than needed.
Key insight: the horizontal coordinate of a node is a cumulative offset - root 0, left child subtracts 1 from its parent, right child adds 1. Nodes sharing a column must appear from the smallest depth upward.
BFS is the right tool: it visits nodes level by level, so the first time a column bucket is written, it is from the smallest row, satisfying the top-to-bottom rule with no depth sorting at all.
Use a hash map keyed by column to a list of node values, populated by a queue that carries (node, column) pairs. After the traversal, sort the column keys ascending and flatten the buckets in that order.
Visual walkthrough for the tree [3, 9, 20, null, null, 15, 7]:
- level 0: (3, col 0) -> {0:[3]}
- level 1: (9, col -1), (20, col 1) -> {-1:[9], 0:[3], 1:[20]}
- level 2: (15, col 0), (7, col 2) -> {-1:[9], 0:[3,15], 1:[20], 2:[7]}
- sorted keys [-1, 0, 1, 2] -> [[9], [3, 15], [20], [7]]
Edge cases: empty tree returns []; a single node returns [[val]]; a skewed tree keeps every node in its own column - the bucket keys stay in sorted order regardless of shape.
Optimal Approach
Run a breadth-first search carrying a column offset with each node. The root enters at column 0, a left child at parent column minus 1, and a right child at parent column plus 1. Append each node's value to the bucket for its column. When BFS finishes, sort the column keys ascending and return the buckets in that order.
Walkthrough for the tree with root 1, left child 2, right child 3, where 2's left child is 4 and 3's children are 5 and 6:
- Level 0: pop 1 at col 0 -> bucket 0 = [1]. Enqueue 2 (col -1), 3 (col 1).
- Level 1: pop 2 at col -1 -> bucket -1 = [2]. Enqueue 4 (col -2). Pop 3 at col 1 -> bucket 1 = [3]. Enqueue 5 (col 0), 6 (col 2).
- Level 2: pop 4 -> bucket -2 = [4]. Pop 5 -> bucket 0 = [1, 5]. Pop 6 -> bucket 2 = [6].
- Sorted keys [-2, -1, 0, 1, 2] -> [[4], [2], [1, 5], [3], [6]].
Time: O(n log k) for sorting k distinct columns, effectively O(n) when the tree is balanced; space: O(n).
What Trips People Up in Real Interviews
Using DFS and then discovering the top-to-bottom tiebreak breaks. Depth-first order can reach a deeper node in a column before a shallower one from another branch. Use BFS so rows are naturally ordered.
Forgetting to sort the column keys. A hash map is unordered - without sorting, columns are emitted in arbitrary insertion order instead of left to right.
Not clarifying which variant you are solving. LeetCode 987 sorts equal-row, same-column nodes by value and requires (row, col, value) triplets; this 314-style problem only needs top-to-bottom. Confirm before coding.
Storing only the value in the queue instead of the node. You cannot descend into children without the node reference - the queue must hold (node, column) pairs.
Ignoring the null-root return. Running BFS on a null root and then indexing the bucket map crashes. Return [] immediately.
Solution Code
from collections import defaultdict, deque
def verticalOrder(root):
if not root:
return []
cols = defaultdict(list)
q = deque([(root, 0)])
while q:
node, col = q.popleft()
cols[col].append(node.val)
if node.left:
q.append((node.left, col - 1))
if node.right:
q.append((node.right, col + 1))
return [cols[col] for col in sorted(cols)]Frequently Asked Questions
What is the Binary Tree Vertical Order Traversal problem?
Group the nodes of a binary tree by horizontal column, where the root sits at column 0, left children shift one column lower, and right children shift one column higher. Return the columns sorted left to right, each column ordered top to bottom - the Apple staple that combines BFS with a hash map.
How do you solve Binary Tree Vertical Order Traversal?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Binary Tree Vertical Order Traversal?
Binary Tree Vertical Order Traversal is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Binary Tree Vertical Order Traversal?
- Using DFS and then discovering the top-to-bottom tiebreak breaks. Depth-first order can reach a deeper node in a column before a shallower one from another branch. Use BFS so rows are naturally ordered.
- Forgetting to sort the column keys. A `hash map` is unordered - without sorting, columns are emitted in arbitrary insertion order instead of left to right.
- Not clarifying which variant you are solving. LeetCode 987 sorts equal-row, same-column nodes by value and requires (row, col, value) triplets; this 314-style problem only needs top-to-bottom. Confirm before coding.
- Storing only the value in the queue instead of the node. You cannot descend into children without the node reference - the queue must hold (node, column) pairs.
- Ignoring the null-root return. Running BFS on a null root and then indexing the bucket map crashes. Return `[]` immediately.