Vertical Order Traversal of a Binary Tree
Asked at Salesforce
Problem
Given a binary tree, return the vertical order traversal of its nodes values. For each column from left to right, nodes are ordered by their row (top to bottom), and nodes at the same position are sorted by value. This requires coordinating column, row, and value ordering simultaneously.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | HARD | View all Salesforce questions → |
How to Think About It
Use DFS or BFS to assign column and row coordinates to every node
Store nodes in a map keyed by column, then by row within each column
For nodes at the same column and row, sort them by value before adding to result
BFS is preferred to naturally process nodes top-to-bottom within each column
Collect all (col, row, value) triples and sort by col, then row, then value
Optimal Approach
Perform a BFS or DFS traversal, tracking the column and row of each node. Store each node as a tuple of (column, row, value) in a list. Sort the list by column first, then by row, then by value. Group consecutive entries with the same column into sub-lists to form the result. BFS is preferred because it naturally processes nodes level by level, giving a more intuitive row ordering. The key insight is that three-dimensional sorting (col, row, value) produces the correct output.
What Trips People Up in Real Interviews
Clarify the tie-breaking rule: same column and row means sort by value
Ask whether it is vertical traversal (column-first) or top-down (row-first)
Discuss BFS vs DFS: BFS gives natural row ordering, DFS does not
Mention that column can be negative (left subtree), zero (root), positive (right)
Talk about edge case: empty tree returns empty list
Solution Code
from collections import defaultdict, deque
class Solution:
def verticalTraversal(self, root: Optional[TreeNode]) -> list[list[int]]:
nodes = []
queue = deque([(root, 0, 0)])
while queue:
node, col, row = queue.popleft()
if node:
nodes.append((col, row, node.val))
queue.append((node.left, col - 1, row + 1))
queue.append((node.right, col + 1, row + 1))
nodes.sort()
result = []
current_col = None
for col, row, val in nodes:
if col != current_col:
result.append([])
current_col = col
result[-1].append(val)
return resultFrequently Asked Questions
What is the Vertical Order Traversal of a Binary Tree problem?
Given a binary tree, return the vertical order traversal of its nodes values. For each column from left to right, nodes are ordered by their row (top to bottom), and nodes at the same position are sorted by value. This requires coordinating column, row, and value ordering simultaneously.
How do you solve Vertical Order Traversal of a Binary Tree?
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 Vertical Order Traversal of a Binary Tree?
Vertical Order Traversal of a Binary Tree is asked at Salesforce. It is a hard difficulty problem.
What are common mistakes on Vertical Order Traversal of a Binary Tree?
- Clarify the tie-breaking rule: same column and row means sort by value
- Ask whether it is vertical traversal (column-first) or top-down (row-first)
- Discuss BFS vs DFS: BFS gives natural row ordering, DFS does not
- Mention that column can be negative (left subtree), zero (root), positive (right)
- Talk about edge case: empty tree returns empty list