314. Binary Tree Vertical Order Traversal
Asked at Apple
Difficulty
Medium
Time
O(n log k)
Space
O(n)
Pattern
Hash Table
Companies
1
Problem
You are given the root of a binary tree. Imagine drawing the tree on paper and dropping a vertical line through every node. Each line is a column. Return the node values grouped by column, reading the columns from left to right.
The root sits in column 0. A left child moves one column to the left (column minus 1), and a right child moves one column to the right (column plus 1). This offset adds up as you go down the tree, so a node's column is the sum of all the left/right steps taken to reach it.
Inside one column, values must be listed top to bottom — smaller depth first. If two nodes share the same row and the same column (this can happen), the left one comes first. The answer is a list of lists: one inner list per column, in left-to-right order.
Columns come from horizontal offsets
Constraints
- ●
The number of nodes is in the range [0, 100] - ●
-100 <= Node.val <= 100
Examples
root = [3,9,20,null,null,15,7][[9],[3,15],[20],[7]]root = [3,9,8,4,0,1,7][[4],[9],[3,0,1],[8],[7]]root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6][[4],[2,5],[1,10,9,6],[3],[11]]Asked At
1 companies| 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.
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).
BFS fills one row of buckets at a time
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
O(n log k) timefrom 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 runs in O(n log k) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.