Vertical Order Traversal
Given the root of a binary tree, return the vertical order traversal. Place each node at position (row, col): the root is (0, 0), a left child is at (row + 1, col - 1) and a right child at (row + 1, col + 1).
Return the nodes grouped by column, from the leftmost column to the rightmost. Within a column, sort by row (top to bottom), and if two nodes share the same row and column, sort by value.
Constraints:
- The number of nodes is in the range
[1, 1000]. 0 <= Node.val <= 1000
Intuition
1 12 / \3 2 34 / \ \5 4 5 6Columns: node 4 is at column -2, node 2 at -1, nodes 1 and 5 at column 0, node 3 at column 1, node 6 at column 2. Expected output: [[4], [2], [1, 5], [3], [6]] (node 1 is in row 0 and node 5 in row 2, so 1 comes first).
So each node has a column and a row. If we record the triple (column, row, value) for every node, the answer is just those triples grouped by column and sorted by (row, value).
Approach: DFS + Map by Column
- Walk the tree (any traversal). For each node at
(row, col), store(row, value)in a sorted map keyed by column. - Go to the left child with
(row + 1, col - 1)and the right child with(row + 1, col + 1). - After the walk, iterate the map in increasing column order. For each column, sort its list by row, then value, and output the values.
A sorted map (map in C++, TreeMap in Java) keeps the columns ordered. In languages without one, sort the column keys at the end. The sort inside each column is what handles the tie rule: same row and column means smaller value first.
Code
class Solution {void dfs(TreeNode* node, int row, int col, map<int, vector<pair<int, int>>>& cols) {if (node == nullptr) return;cols[col].push_back({row, node->val});dfs(node->left, row + 1, col - 1, cols);dfs(node->right, row + 1, col + 1, cols);}public:vector<vector<int>> verticalTraversal(TreeNode* root) {map<int, vector<pair<int, int>>> cols;dfs(root, 0, 0, cols);vector<vector<int>> ans;for (auto& entry : cols) {auto& nodes = entry.second;sort(nodes.begin(), nodes.end());vector<int> column;for (auto& p : nodes) column.push_back(p.second);ans.push_back(column);}return ans;}};
Complexity
The walk is O(n). Sorting the entries, split across columns, costs O(n log n) in total.
The map stores one entry per node. Recursion adds O(h).