Vertical Order Traversal of a Binary Tree
Reported by candidates from Amazon's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Amazon reportedly served this one in July 2026, and the input size is the first thing to read. Up to 10^5 nodes means you can't re-scan the tree for every column or sort everything by value. It's a vertical order traversal of a binary tree, and the tree pattern is a single BFS with column tracking. The twist is the tie rule: nodes sharing a row and column keep BFS encounter order, not value order. If you've seen the LeetCode version, don't trust muscle memory. StealthCoder sits invisibly on your screen as a safety net if you blank mid-assessment.
The problem
You are given a binary tree serialized as a level-order array levelOrder. Each non-null token is a signed decimal integer, and the token "null" denotes a missing child. Place the root at row 0, column 0. For a node at row r, column c: Its left child is at row r + 1, column c - 1. Its right child is at row r + 1, column c + 1. Return the node values grouped by column from the smallest column to the largest. Within one column, order nodes by increasing row. When multiple nodes share the same row and column, preserve their breadth-first left-to-right encounter order; do not sort them by value. If the tree is empty, return an empty list. Function verticalOrder(levelOrder: String[]) → List<List<Integer>> Examples Example 1 levelOrder = ["3","9","20","null","null","15","7"] return = [[9],[3,15],[20],[7]] The columns from left to right are -1, 0, 1, and 2. Example 2 levelOrder = ["1","2","3","4","6","5","7"] return = [[4],[2],[1,6,5],[3],[7]] Nodes 6 and 5 share row 2 and column 0. Breadth-first left-to-right encounter order places 6 before 5. Example 3 levelOrder = [] return = [] An empty tree has no columns. Constraints 0 <= non-null node count <= 10^5. Every non-null token represents a signed 32-bit integer. levelOrder is a valid level-order serialization using "null" markers.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is one breadth-first pass. Parse the level-order array into nodes using a queue, then run BFS carrying (node, column). Append each value to a hash map keyed by column, and track min and max column. BFS already visits rows top to bottom and left to right, so insertion order inside each column gives you the required answer with no sorting. That's O(n). The common pitfall is copying the LeetCode solution that sorts ties by value, which fails Example 2 where 6 must come before 5. Another trap is building the tree wrong from the "null" tokens, since children are assigned only for non-null parents. Also, skip recursion at this size, because a skewed tree can overflow the stack. If you freeze on the parsing or tie rule during the live OA, StealthCoder is the hedge that reads the problem and hands you a working solution.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Vertical Order Traversal of a Binary Tree cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as vertical order traversal of a binary tree. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Amazon's OA.
Amazon reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Vertical Order Traversal of a Binary Tree FAQ
What's the trick to this Amazon vertical order problem?+
Run BFS from the root while tracking each node's column. Store values in a map from column to list. Because BFS visits in row order and left to right, each list is already correctly ordered. Then read columns from min to max. No sorting needed.
How is this different from the LeetCode version?+
LeetCode's version sorts nodes sharing the same row and column by value. This one says don't. You keep BFS encounter order instead. If you sort by value, Example 2 breaks, because 5 would land before 6. Read the tie rule carefully before coding.
Why can't I use recursive DFS here?+
You can, but you'd need to track rows and then sort by row, and ties get harder to keep in BFS order. With up to 10^5 nodes, a skewed tree can also overflow the call stack. BFS is simpler, safer, and linear.
How do I build the tree from the levelOrder array?+
Use a queue of parent nodes. Create the root from the first token, then for each parent take the next two tokens as left and right children. Skip "null" tokens without enqueuing. Handle the empty array first and return an empty list.
How do I prepare for this in 48 hours?+
Write the BFS with column tracking from scratch twice, including the array-to-tree parsing. Test with the three examples, especially the empty tree and the tie case. Know your complexity: O(n) time with a hash map, plus tracking min and max column to avoid sorting keys.