On this page

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 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Columns: 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

  1. Walk the tree (any traversal). For each node at (row, col), store (row, value) in a sorted map keyed by column.
  2. Go to the left child with (row + 1, col - 1) and the right child with (row + 1, col + 1).
  3. 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

Time: O(n log n)

The walk is O(n). Sorting the entries, split across columns, costs O(n log n) in total.

Space: O(n)

The map stores one entry per node. Recursion adds O(h).

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Each node gets a column and a row: left child is column minus one, right child is column plus one, and both go one row down. I walk the tree with DFS and store row and value in a map keyed by column. Because DFS order is not row order, I sort each column at the end by row and then by value, which also handles the tie rule for nodes sharing a row and column. I output the columns from the smallest key to the largest. The walk is O of n and the sorting makes it O of n log n, with O of n space for the map."
Next TopicTop View of Binary Tree