Binary Tree Vertical Order Traversal
Medium · Trees · Hash Table · Tree · Depth-First Search · Breadth-First Search · Sorting · Binary Tree
Problem
Given the root of a binary tree, return its values column by column, from the leftmost column to the rightmost. The empty tree gives [].
The root is in column 0. A left child is one column to the left of its parent (c - 1) and a right child one column to the right (c + 1). Within a column, list the values from top to bottom. When two nodes share both a row and a column — a left-then-right path and a right-then-left path end in the same place — list them from left to right, the order a breadth-first walk meets them.
That tie rule is where solutions go wrong. A depth-first walk can reach a deep node in the left subtree before a shallow node in the right subtree of the same column, so collecting values in depth-first order puts them out of place. And sorting ties by value is a different problem (LeetCode 987).
The node type and two helpers are provided:
Examples
Input: root = [3,9,20,None,None,15,7] Output: [[9],[3,15],[20],[7]]
9 is in column -1; 3 and 15 in column 0, with 3 on top; 20 in column 1 and 7 in column 2.
Input: root = [3,9,8,4,0,1,7,None,None,None,2,5] Output: [[4],[9,5],[3,0,1],[8,2],[7]]
0 and 1 share row 2 and column 0, and 0 is further left, so it comes first. In column 1, 8 (row 1) is listed before 2 (row 3), even though a depth-first walk reaches 2 first.
Constraints
- 0 <= number of nodes <= 100
- -100 <= Node.val <= 100
Approaches
- A full sweep of the tree for every column — time O(n · c), O(n²) worst case, space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
