What happens when two nodes have the same row and column?

Their values are arranged in ascending order. This is why storing only the horizontal position is not sufficient.

How is Vertical Order Traversal different from Top View?

Top View keeps only the shallowest visible node from each vertical line. Vertical Order Traversal includes all nodes belonging to every vertical line.

Can DFS also be used for Vertical Order Traversal?

Yes. DFS can record the row and column of every node. However, the final ordering must still account for column, row, and value-based ties.

Why is this more involved than simply grouping nodes by horizontal distance?

Nodes within a column must also follow row order, and multiple nodes can occupy the same row and column. Therefore, column, row, and value ordering must all be handled correctly.

Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, return its vertical order traversal from left to right.

A coordinate is assigned to every node:

The root is placed at row = 0, column = 0.
The left child of a node at (row, column) is placed at (row + 1, column - 1).
The right child is placed at (row + 1, column + 1).

Nodes are grouped according to their column.

Within each column:

Nodes with a smaller row appear first.
If multiple nodes have the same row and column, their values appear in ascending order.

The traversal is returned as a list of columns from the smallest column to the largest.

Example 1

Input:
root = [3, 9, 20, null, null, 15, 7]

Output:
[[9], [3, 15], [20], [7]]

Explanation:
Node 9 lies at column -1. Nodes 3 and 15 lie at column 0, with 3 appearing first because it has the smaller row. Node 20 lies at column 1, and node 7 lies at column 2.

Example 2

Input:
root = [1, 2, 3, 4, 6, 5, 7]

Output:
[[4], [2], [1, 5, 6], [3], [7]]

Explanation:
Nodes 5 and 6 occupy the same row and column. Their values are therefore placed in ascending order as 5, 6. The columns are returned from left to right.

Practice it by yourself before moving onto the solutionTry now

Approach 1

Vertical traversal depends on three pieces of information:

column → row → value

The column determines the vertical line to which a node belongs. The row determines its top-to-bottom position within that column, while the node value resolves ties when multiple nodes occupy the same row and column.

Therefore, every node can be stored as:

(column, row, value)

Once all nodes have been collected, these entries can be sorted by column, then row, and finally value. This directly produces the ordering required by the problem.

While the sorted entries are being converted into the final result, a variable previousColumn is used to remember the column of the previously processed entry. Whenever the current column differs from previousColumn, a new vertical list is started. This allows consecutive nodes belonging to the same column to be grouped together efficiently.

Algorithm

The tree is traversed while the row and column of every node are tracked, and each node is stored as (column, row, value) so that all required ordering information is preserved.
For every left child, the coordinates are transformed to (row + 1, column - 1), while every right child is assigned (row + 1, column + 1).
After traversal, all stored entries are sorted first by column, then by row, and finally by node value so that the required vertical ordering is obtained.
A variable previousColumn is maintained while the sorted entries are processed. Whenever a different column is encountered, a new vertical list is created.
Nodes having the same column are appended to the current vertical list, and all completed lists are stored from the smallest column to the largest.
The grouped vertical lists are returned as the final traversal.Dry Run

Vertical Traversal Appraoch 1 Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Stores every node with its
  // column, row, and value.
  void dfs(
      TreeNode* node,
      int row,
      int column,
      vector<tuple<int, int, int>>& nodes
  ) {
      if (node == nullptr) {
          return;
      }
29
      nodes.push_back({
          column,
          row,
          node->val
      });
35
      // Moving left increases the row
      // and decreases the column.
      dfs(
          node->left,
          row + 1,
          column - 1,
          nodes
      );
44
      // Moving right increases both
      // the row and column.
      dfs(
          node->right,
          row + 1,
          column + 1,
          nodes
      );
  }
54
55public:
  // Returns nodes grouped by vertical
  // columns from left to right.
  vector<vector<int>> verticalTraversal(
      TreeNode* root
  ) {
      if (root == nullptr) {
          return {};
      }
64
      vector<tuple<int, int, int>> nodes;
66
      dfs(root, 0, 0, nodes);
68
      // Tuple sorting automatically follows
      // column, then row, then value.
      sort(nodes.begin(), nodes.end());
72
      vector<vector<int>> answer;
      int previousColumn = INT_MIN;
75
      // A new group is started whenever
      // the column changes.
      for (auto& entry : nodes) {
          auto [column, row, value] = entry;
80
          if (column != previousColumn) {
              answer.push_back({});
              previousColumn = column;
          }
85
          answer.back().push_back(value);
      }
88
      return answer;
  }
91};
92
93int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(9);
  root->right = new TreeNode(20);
  root->right->left = new TreeNode(15);
  root->right->right = new TreeNode(7);
99
  Solution solution;
101
  vector<vector<int>> answer =
      solution.verticalTraversal(root);
104
  for (auto& column : answer) {
      for (int value : column) {
          cout << value << " ";
      }
      cout << endl;
  }
111
  return 0;
113}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of nodes in the binary tree. All N nodes are stored and then sorted according to their column, row, and value.

Space Complexity: O(N), where N is the number of nodes in the binary tree. Coordinate information for all nodes may need to be stored before the final vertical groups are constructed.

Approach 2

Instead of collecting every node first and sorting everything afterward, the nodes can be organized according to their coordinates during traversal itself.

A nested ordered structure is used:

map<int, map<int, multiset<int>>>

Each level of this structure has a specific purpose:

The outer map uses the column as its key, so vertical lines remain ordered from left to right.
The inner map uses the row as its key, so nodes within each column remain ordered from top to bottom.
The multiset stores values of nodes that share the exact same (column, row) position and automatically keeps those values in ascending order.

This structure directly matches the ordering rules of the problem and avoids requiring one global sort over all node coordinates.

BFS can then be used to traverse the tree while carrying each node's row and column.

Algorithm

If the root is non-null, a queue is initialized with the root at (row = 0, column = 0) so that coordinate information can be carried during BFS.
A nested ordered structure of the form column → row → sorted values is maintained, allowing columns, rows, and equal-position values to remain ordered automatically.
Whenever a node is removed from the queue, its value is inserted into the collection corresponding to its current (column, row) position.
For every left child, (row + 1, column - 1) is assigned, while every right child is assigned (row + 1, column + 1), preserving their correct vertical positions.
After traversal, the outer map is processed from the smallest column to the largest, while each inner map is processed from the smallest row to the largest. Values stored in each multiset are appended in their already sorted order.
Each completed column is added to the final result, producing the required vertical traversal from left to right.

Dry Run

Vertical Traversal Appraoch 2 Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17public:
  // Organizes nodes directly by
  // column, row, and sorted value.
  vector<vector<int>> verticalTraversal(
      TreeNode* root
  ) {
      if (root == nullptr) {
          return {};
      }
26
      // Outer map orders columns, inner map
      // orders rows, multiset sorts equal positions.
      map<int, map<int, multiset<int>>> nodes;
30
      queue<pair<TreeNode*, pair<int, int>>> q;
32
      q.push({
          root,
          {0, 0}
      });
37
      // BFS carries the coordinate
      // of every visited node.
      while (!q.empty()) {
          auto current = q.front();
          q.pop();
43
          TreeNode* node = current.first;
          int column = current.second.first;
          int row = current.second.second;
47
          nodes[column][row].insert(
              node->val
          );
51
          // A left child moves one row down
          // and one column to the left.
          if (node->left != nullptr) {
              q.push({
                  node->left,
                  {column - 1, row + 1}
              });
          }
60
          // A right child moves one row down
          // and one column to the right.
          if (node->right != nullptr) {
              q.push({
                  node->right,
                  {column + 1, row + 1}
              });
          }
      }
70
      vector<vector<int>> answer;
72
      // Nested iteration preserves column,
      // row, and ascending-value order.
      for (auto& columnEntry : nodes) {
          vector<int> columnValues;
77
          for (auto& rowEntry : columnEntry.second) {
              for (int value : rowEntry.second) {
                  columnValues.push_back(value);
              }
          }
83
          answer.push_back(columnValues);
      }
86
      return answer;
  }
89};
90
91int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(9);
  root->right = new TreeNode(20);
  root->right->left = new TreeNode(15);
  root->right->right = new TreeNode(7);
97
  Solution solution;
99
  vector<vector<int>> answer =
      solution.verticalTraversal(root);
102
  for (auto& column : answer) {
      for (int value : column) {
          cout << value << " ";
      }
      cout << endl;
  }
109
  return 0;
111}

Complexity Analysis

Time Complexity: O(N log N) in the worst case, where N is the number of nodes in the binary tree. Every node is inserted into ordered maps and multisets, and these operations can require logarithmic time.

Space Complexity: O(N), where N is the number of nodes in the binary tree. The nested map structure and BFS queue may together store information for up to all nodes.

Interview follow-up Questions

The column determines which vertical line a node belongs to, while the row determines its top-to-bottom position within that vertical line.

Vertical Order Traversal of a Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree

Vertical Order Traversal of a Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why are both row and column required?

What happens when two nodes have the same row and column?

How is Vertical Order Traversal different from Top View?

Can DFS also be used for Vertical Order Traversal?

Why is this more involved than simply grouping nodes by horizontal distance?

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree