Compute vertical order of a BST
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Compute the vertical order traversal of a binary search tree. Define coordinates so the root is at column 0, row 0; the left child is (col−1, row+
1) and the right child is (col+1, row+
1). Return a list of columns from the smallest to the largest column index, where each column is a list of node values ordered by increasing row. For nodes that share the same (row, column), break ties by the order they would be visited in a left-to-right breadth-first traversal. Provide an algorithm, justify its time and space complexity, and implement a function that returns the required structure. Follow-ups:
(
1) How would you handle extremely skewed trees to avoid worst-case recursion depth?
(
2) How would you stream results if the tree is too large to fit in memory?
Quick Answer: This question evaluates understanding of binary tree traversals and coordinate-based ordering, including tie-breaking by breadth-first visitation order, plus competency in algorithmic time and space complexity analysis and strategies for handling deep recursion and streaming large inputs.
You are given a binary tree encoded as a level-order array `levelOrder` (LeetCode style): index 0 is the root, and children are listed left-to-right level by level, using `null`/`None` to mark missing nodes. (The original interview asked about a BST, but vertical order does not depend on the BST property, so any binary tree shape is accepted.)
Assign coordinates so the root sits at column 0, row 0; a node's left child is at (col - 1, row + 1) and its right child is at (col + 1, row + 1).
Return the vertical order traversal: a list of columns ordered from the smallest column index to the largest. Each column is a list of node values ordered by increasing row. When two nodes share the same (row, column), break ties by the order in which they are visited in a standard left-to-right breadth-first (level-order) traversal of the tree.
Return an empty list for an empty tree.
Follow-ups to discuss (not graded by tests): (1) handling extremely skewed trees to avoid worst-case recursion depth — use an explicit BFS/iterative stack instead of recursion; (2) streaming results when the tree is too large for memory — process column buckets externally / on disk keyed by column.
Constraints
- 0 <= number of nodes <= 10^4
- Node values fit in a 32-bit signed integer
- The input is a valid LeetCode-style level-order encoding (null marks a missing node; no orphan subtrees)
- Coordinates: root at (col 0, row 0); left child (col-1, row+1); right child (col+1, row+1)
Examples
Input: ([9, 5, 13, 2, 7, 11, 15],)
Expected Output: [[2], [5], [9, 7, 11], [13], [15]]
Explanation: Balanced BST. Column -2 has {2}, col -1 has {5}, col 0 has root 9 (row0) then 7 and 11 (both row2, BFS order 7 before 11), col 1 has {13}, col 2 has {15}.
Input: ([],)
Expected Output: []
Explanation: Empty tree -> empty result.
Hints
- Vertical order does not depend on the BST property — treat the input as a general binary tree and assign each node a (column, row) coordinate.
- Do a single breadth-first traversal starting at the root with col=0, row=0; push the left child with col-1 and the right child with col+1, both at row+1.
- Bucket nodes by column. Because BFS already visits nodes in increasing-row, left-to-right order, recording an insertion index per node lets you break ties for nodes sharing the same (row, column).
- Finally, output columns from the smallest to the largest key; within each column sort by (row, insertion-index).