How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Compute vertical order of a BST | Meta Coding Question

Quick Overview

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.

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.

Input: ([42],)

Expected Output: [[42]]

Explanation: Single node sits at column 0.

Input: ([10, 5, 20, None, None, 15, 30],)

Expected Output: [[5], [10, 15], [20], [30]]

Explanation: 5 is the left child (col -1). 20's left child 15 lands back at col 0 with row 2, so column 0 holds [10, 15] (10 at row0 before 15 at row2). 20 at col +1, 30 at col +2.

Input: ([8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15],)

Expected Output: [[1], [2], [4, 3, 5, 9], [8, 6, 10], [12, 7, 11, 13], [14], [15]]

Explanation: Full balanced tree depth 4. Column 0 collects root 8 (row0), then 6 and 10 (row2), exercising left-to-right BFS placement; column -1 collects 4 (row1), then 3,5,9 (row3) in BFS order.

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).

Quick Overview