DSA problem
Binary Tree Vertical Order Traversal
Given the root of a binary tree, return the vertical order traversal of its nodes' values. The vertical order assigns each node a column index: the root has column 0, every left child decrements its parent's column by 1, and every right child increments it by 1. Nodes in the same column are reported in the order they are encountered during a level-order BFS (top to bottom; if two nodes share the same row and column the leftmost — i.e. the earlier-enqueued — comes first).
The trick is to combine BFS with a column-keyed multimap. As we BFS the tree we attach a column index to every node we enqueue. For each dequeued node we append its value to the bucket for its column. Because BFS visits all nodes at depth d before any node at depth d + 1, every bucket naturally accumulates its values in top-to-bottom order.
To emit the final answer we just need the columns in ascending order. A TreeMap in Java does this directly; in C++ std::map keeps keys sorted. In Python, JavaScript, and TypeScript we use a hash map plus two trackers minCol and maxCol, then iterate from minCol to maxCol to assemble the result. Time is O(n) for the BFS, plus O(n) or O(n log n) to emit the columns depending on which container we use; space is O(n).
Examples
root = [3,9,20,null,null,15,7][[9],[3,15],[20],[7]]root = [3,9,8,4,0,1,7][[4],[9],[3,0,1],[8],[7]]root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6][[4],[2,5],[1,9,10],[3,6],[11]]Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
- When two nodes occupy the same column the one encountered earlier in BFS comes first.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.