Binary Tree Vertical Order with Stable Ties
Updated
Problem statement
Given the root of a binary tree, return its vertical order as an array of columns. Place the root at row 0, column 0. A left child is one row lower and one column to the left; a right child is one row lower and one column to the right.
For this exercise, assume columns are returned from leftmost to rightmost. Within a column, return nodes from top to bottom. Nodes in the same row and column keep their left-to-right positional order in the tree; equivalently, visit each level from left to right. Do not sort tied nodes by value. Keep repeated values as separate entries.
Return an empty array for an empty tree.
Follow-up: A single output list
How would you return one flat list instead of separate column lists? Keep the same column and node order, and concatenate the columns. For the second example, the flat result is [4,2,1,6,5,3,7].
Function
verticalOrder(root: TreeNode) → int[][]Examples
Example 1
root = [3,9,20,null,null,15,7]return = [[9],[3,15],[20],[7]]The columns are [9], [3,15], [20] and [7], from left to right.
Example 2
root = [1,2,3,4,6,5,7]return = [[4],[2],[1,6,5],[3],[7]]The nodes 6 and 5 share row 2 and column 0. Node 6 is to the left of node 5, so the middle column is [1,6,5], not [1,5,6].
Example 3
root = []return = []An empty tree has no columns.
Example 4
root = [8,8,8,null,8,8,null]return = [[8],[8,8,8],[8]]Repeated values represent distinct nodes. The middle column contains the root followed by both grandchildren.
Constraints
- For this exercise, assume the tree contains between
0and2000nodes. - For this exercise, assume each node value is between
-10^9and10^9, inclusive. - The input is a valid binary tree. Its displayed array uses level order, with
nullfor missing children.
More Meta Onsite Interview questions
- Deterministic K-Means AssignmentsPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Linear Layer Forward and Backward PassesONSITE INTERVIEW · Seen Sep 2026
- Reservoir Sampling with Recorded DrawsONSITE INTERVIEW · Seen Sep 2026
- Stochastic Gradient Descent with MomentumONSITE INTERVIEW · Seen Sep 2026
- Top K Largest Values with a HeapONSITE INTERVIEW · Seen Sep 2026
- Multi-Head Attention Forward PassPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Mutual-Friend RecommendationsONSITE INTERVIEW · Seen Sep 2026
- Partition a Card Deck into FifteensONSITE INTERVIEW · Seen Sep 2026
- Insert into a Sorted Circular ListONSITE INTERVIEW · Seen Aug 2026
- Maximum Stock Profit with Transaction LimitsONSITE INTERVIEW · Seen Aug 2026
Similar questions at other companies
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- Bottom View of a Binary TreeOracle · PHONE SCREEN · ONSITE INTERVIEWOracle interview questions
- Vertical Order Traversal of a Binary TreeAmazon · ONSITE INTERVIEW
- Binary Tree Vertical Order TraversalBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Top View of a Binary TreeInMobi · ONSITE INTERVIEWInMobi interview questions
- Count LevelsBlackRock · OABlackRock interview questions
- Insert an Employee into an Organization HierarchyWaymo · PHONE SCREENWaymo interview questions
- Everyone Under a ManagerAdobe · PHONE SCREENAdobe interview questions
- Team Cost Under a ManagerRippling · PHONE SCREENRippling interview questions
- Path Between Two Binary-Tree NodesSnowflake · PHONE SCREENSnowflake interview questions