Log inSign up
hardleetcodeNot Started

Vertical Order Traversal of a Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left child will be at (row + 1, col - 1) and its right child will be at (row + 1, col + 1). Root is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. If two or more nodes have the same row and col, they should be sorted by their values in ascending order.

Example 1 · Example 1: Standard Tree:

Input: root = [3, 9, 20, null, null, 15, 7] Tree: 3 / \ 9 20 / \ 15 7
Output: [[9], [3, 15], [20], [7]]
Explanation: Col -1: [9]. Col 0: 3 (row 0), 15 (row 2). Col 1: [20]. Col 2: [7].

Example 2 · Example 2: Overlapping Nodes Tie-Breaker:

Input: root = [1, 2, 3, 4, 6, 5, 7] Tree: 1 / \ 2 3 / \ / \ 4 6 5 7
Output: [[4], [2], [1, 5, 6], [3], [7]]
Explanation: At col 0, row 2: nodes 5 and 6 overlap. Sorted by value: [5, 6]. Col 0 is [1, 5, 6].

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model 2D coordinate space (row, col) on binary trees.
  • Implement multi-criterion sorting (col -> row -> val).
  • Structure nested tree maps or tuple sort comparator cleanly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Vertical column order with row and value tie-breaking.
  • Cartesian coordinate mapping on trees.
  • Multi-level sorting criteria.

Algorithmic Decision Tree:

  • Assign (col, row) to each node.
  • Group by col.
  • Sort each column by row asc, then val asc.

Connected Patterns:

Top View of Binary TreeBottom View of Binary TreeBinary Tree Level Order Traversal

1. Collect Tuples and Sort (Flat Tuple Array)

Intuition

Traverse tree with DFS/BFS and collect tuple {col, row, val} for every node. Sort the array with comparator (c1 < c2 || (c1 == c2 && (r1 < r2 || (r1 == r2 && v1 < v2)))). Group adjacent elements with same col.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Traverse tree collecting tuples (col, row, val).
  2. Step 2: Sort tuples array by col asc, row asc, val asc.
  3. Step 3: Group adjacent elements with same col into sublists.
  4. Step 4: Return result list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 struct NodeInfo { int col, row, val; };
9 void dfs(TreeNode* node, int col, int row, vector<NodeInfo>& nodes) {
10 if (!node) return;
11 nodes.push_back({col, row, node->val});
12 dfs(node->left, col - 1, row + 1, nodes);
13 dfs(node->right, col + 1, row + 1, nodes);
14 }
15public:
16 vector<vector<int>> verticalTraversal(TreeNode* root) {
17 vector<NodeInfo> nodes;
18 dfs(root, 0, 0, nodes);
19 sort(nodes.begin(), nodes.end(), [](const NodeInfo& a, const NodeInfo& b) {
20 if (a.col != b.col) return a.col < b.col;
21 if (a.row != b.row) return a.row < b.row;
22 return a.val < b.val;
23 });
24 vector<vector<int>> res;
25 for (int i = 0; i < nodes.size(); ++i) {
26 if (i == 0 || nodes[i].col != nodes[i - 1].col) {
27 res.push_back({});
28 }
29 res.back().push_back(nodes[i].val);
30 }
31 return res;
32 }
33};
34
35int main() {
36 // Sample driver execution
37 cout << "Execution completed successfully." << endl;
38 return 0;
39}
40

Time & Space Complexity

  • Time complexity: O(n log n) — Sorting n tuples takes O(n log n).
  • Space complexity: O(n) — Tuple array takes O(n) space.

2. BFS with Queue of (Node, Col, Row)

Intuition

Level order queue processes nodes top-to-bottom. Store nodes in map[col] = list of (row, val). Sort each column list by row asc, then val asc.

When to apply: Iterative queue-based traversal.

Algorithm

  1. Step 1: Queue stores (node, col, row).
  2. Step 2: Collect into map[col].push_back({row, node.val}).
  3. Step 3: Sort each column's list by row then val.
  4. Step 4: Return sorted columns.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> verticalTraversal(TreeNode* root) {
10 if (!root) return {};
11 map<int, vector<pair<int, int>>> colMap;
12 queue<tuple<TreeNode*, int, int>> q;
13 q.push({root, 0, 0});
14 while (!q.empty()) {
15 auto [node, col, row] = q.front(); q.pop();
16 colMap[col].push_back({row, node->val});
17 if (node->left) q.push({node->left, col - 1, row + 1});
18 if (node->right) q.push({node->right, col + 1, row + 1});
19 }
20 vector<vector<int>> res;
21 for (auto& [col, vec] : colMap) {
22 sort(vec.begin(), vec.end());
23 vector<int> colVals;
24 for (auto& [row, val] : vec) colVals.push_back(val);
25 res.push_back(colVals);
26 }
27 return res;
28 }
29};
30
31int main() {
32 // Sample driver execution
33 cout << "Execution completed successfully." << endl;
34 return 0;
35}
36

Time & Space Complexity

  • Time complexity: O(n log n) — Sorting elements within columns takes O(n log n) total.
  • Space complexity: O(n) — Queue and map store n elements.

3. Nested Multiset Tree Map Structure

Intuition

In C++ and Java, nested sorted maps (TreeMap / multiset) maintain sorted order across all 3 keys (col asc, row asc, val asc) simultaneously on each insertion.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Nested structure nodes[col][row].insert(val).
  2. Step 2: Traverse with DFS/BFS inserting each node.
  3. Step 3: Iterate outer map by col, inner map by row, and multiset by val.
  4. Step 4: Push to answer matrix.

Vertical Traversal Trace for root = [1, 2, 3, 4, 6, 5, 7]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Assign coordinates
Visual state
Values and pointers at this exact step
tree
Root
1 (0,0)
L
2 (-1,1)
R
3 (1,1)

Node order shown; add connections to display explicit tree edges.

col: 0: 1
Check / comparison
Columns: -1 (val 2), 0 (val 1), 1 (val 3)
Decision / next transition
Group into columns.
Why this step matters

Step 1: Assign coordinates. Root 1 is (col:0, row:0). Left 2 is (col:-1, row:1). Right 3 is (col:1, row:1).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> verticalTraversal(TreeNode* root) {
10 map<int, map<int, multiset<int>>> nodes;
11 queue<tuple<TreeNode*, int, int>> q;
12 q.push({root, 0, 0});
13 while (!q.empty()) {
14 auto [node, col, row] = q.front(); q.pop();
15 nodes[col][row].insert(node->val);
16 if (node->left) q.push({node->left, col - 1, row + 1});
17 if (node->right) q.push({node->right, col + 1, row + 1});
18 }
19 vector<vector<int>> res;
20 for (auto& [col, rowMap] : nodes) {
21 vector<int> colVec;
22 for (auto& [row, mset] : rowMap) {
23 colVec.insert(colVec.end(), mset.begin(), mset.end());
24 }
25 res.push_back(colVec);
26 }
27 return res;
28 }
29};
30
31int main() {
32 // Sample driver execution
33 cout << "Execution completed successfully." << endl;
34 return 0;
35}
36

Time & Space Complexity

  • Time complexity: O(n log n) — Multiset insertions take O(log n) each.
  • Space complexity: O(n) — Nested map stores n nodes.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Flat Tuple Array SortO(n log n)O(n)Collect tuples and sort with single comparator.Tuple sorting.
2.BFS Col MapO(n log n)O(n)Bucket nodes into map[col] then sort each bucket.Per-column sort.
3.Nested Multiset Tree MapOptimalO(n log n)O(n)Automated 3-level key sorting via nested maps.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: returns [[root.val]].
  • Nodes with identical (col, row): sorted by value in ascending order.
  • Asymmetric tree: columns correctly spans from leftmost to rightmost.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify the tie-breaker rule: if two nodes have both the same col AND the same row, sort them by value.
  2. Explain the coordinate setup: root is (0, 0), left is (col - 1, row + 1), right is (col + 1, row + 1).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Vertical Order Traversal require sorting by value ONLY when two nodes share both the same column AND the same row?

Back to DSA Sheet