Binary Tree Vertical Order Traversal
01 · Problem
Given the root of a binary tree, return its node values grouped by vertical column, with columns ordered from left to right.
Place the root in column 0; a left child sits one column to the left of its parent and a right child one column to the right. Within each column, list values from top to bottom. If two nodes share the same row and column, list the one that appears further left in level order (that is, the one a breadth-first traversal visiting left children before right children reaches first) before the other. Return an empty list for an empty tree. The tree is given in level-order form, with null marking missing children.
02 · Examples
root = [3,9,20,null,null,15,7]
[[9],[3,15],[20],[7]]
Column -1 holds 9, column 0 holds 3 then 15, column 1 holds 20, and column 2 holds 7.
root = [3,9,8,4,0,1,7]
[[4],[9],[3,0,1],[8],[7]]
Nodes 0 and 1 both sit in column 0 on the same row; 0 comes first because it appears further left in level order.
root = []
[]
An empty tree has no columns.
03 · Constraints
- 01The number of nodes in the tree is in the range [0, 100].
- 02-100 <= Node.val <= 100
- 03The tree is given in level-order form, with null for missing children.
- 04Node values are not necessarily unique.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.