Vertical Order Traversal of Binary Tree in DSA C++

Mental Model

We want to group tree nodes by their vertical columns from left to right, and within each column, nodes are ordered top to bottom.

Analogy: Imagine standing in front of a tree and taking pictures from left to right columns; nodes in the same column appear in the same photo, ordered from top to bottom.

       1
      / \
     2   3
    / \   \
   4   5   6

Columns: -2  -1   0   1   2
Nodes:  4   2   1,5   3   6

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Group nodes by vertical columns from left to right, top to bottom within each column

Step 1: Start BFS from root node 1 at column 0

Column 0: [1]
Queue: [(1,0)]

Why: We begin traversal at root with column index 0

Step 2: Dequeue node 1, enqueue left child 2 at column -1 and right child 3 at column 1

Column 0: [1]
Column -1: []
Column 1: []
Queue: [(2,-1), (3,1)]

Why: Left child is one column left, right child one column right

Step 3: Dequeue node 2, enqueue left child 4 at column -2 and right child 5 at column 0

Column 0: [1]
Column -1: [2]
Column 1: []
Column -2: []
Queue: [(3,1), (4,-2), (5,0)]

Why: Continue BFS, assigning columns accordingly

Step 4: Dequeue node 3, enqueue right child 6 at column 2

Column 0: [1]
Column -1: [2]
Column 1: [3]
Column -2: []
Column 2: []
Queue: [(4,-2), (5,0), (6,2)]

Why: Node 3 has no left child, right child is one column right

Step 5: Dequeue node 4, no children to enqueue

Column 0: [1]
Column -1: [2]
Column 1: [3]
Column -2: [4]
Column 2: []
Queue: [(5,0), (6,2)]

Why: Leaf node, no further nodes to add

Step 6: Dequeue node 5, no children to enqueue

Column 0: [1,5]
Column -1: [2]
Column 1: [3]
Column -2: [4]
Column 2: []
Queue: [(6,2)]

Why: Add node 5 to column 0 list

Step 7: Dequeue node 6, no children to enqueue

Column 0: [1,5]
Column -1: [2]
Column 1: [3]
Column -2: [4]
Column 2: [6]
Queue: []

Why: Add node 6 to column 2 list, traversal complete

Result:

Vertical order traversal:
Column -2: 4
Column -1: 2
Column 0: 1 -> 5
Column 1: 3
Column 2: 6

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<vector<int>> verticalOrderTraversal(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;

    map<int, vector<int>> columnTable; // column index -> nodes
    queue<pair<TreeNode*, int>> q; // node and its column
    q.push({root, 0});

    while (!q.empty()) {
        auto [node, col] = q.front();
        q.pop();
        columnTable[col].push_back(node->val); // add node to its column

        if (node->left) q.push({node->left, col - 1}); // left child column -1
        if (node->right) q.push({node->right, col + 1}); // right child column +1
    }

    for (auto& [col, nodes] : columnTable) {
        result.push_back(nodes); // collect columns in order
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    vector<vector<int>> verticalOrder = verticalOrderTraversal(root);

    for (const auto& col : verticalOrder) {
        for (int val : col) {
            cout << val << " -> ";
        }
        cout << "null" << endl;
    }
    return 0;
}

q.push({root, 0});

Initialize queue with root node at column 0

auto [node, col] = q.front(); q.pop();

Dequeue node and its column for processing

columnTable[col].push_back(node->val);

Add current node's value to its column list

if (node->left) q.push({node->left, col - 1});

Enqueue left child with column one less

if (node->right) q.push({node->right, col + 1});

Enqueue right child with column one more

for (auto& [col, nodes] : columnTable) result.push_back(nodes);

Collect nodes column-wise in order for final result

Output

4 -> null

2 -> null

1 -> 5 -> null

3 -> null

6 -> null

Complexity Analysis

Time: O(n) because we visit each node once during BFS traversal

Space: O(n) to store nodes in the map and queue for BFS

vs Alternative: Compared to DFS with sorting by coordinates, BFS with map is simpler and efficient for vertical order

Edge Cases

Empty tree

Returns empty list without error

DSA C++

if (!root) return result;

Tree with single node

Returns list with one column containing the single node

DSA C++

q.push({root, 0});

Tree with multiple nodes in same column

Nodes appear in order of BFS traversal (top to bottom)

DSA C++

columnTable[col].push_back(node->val);

When to Use This Pattern

When asked to print or group nodes by vertical columns in a binary tree, use vertical order traversal with BFS and column indexing to maintain order.

Common Mistakes

Mistake: Using DFS without tracking node levels can mix order of nodes in same column
Fix: Use BFS to ensure top-to-bottom order within each column

Mistake: Not using a map keyed by column index, causing unordered output
Fix: Use a map or ordered dictionary keyed by column index to collect nodes

Summary

Groups binary tree nodes by vertical columns from left to right, top to bottom.

Use when you need to print or analyze nodes column-wise in a tree.

Track column indices during BFS to maintain correct vertical order.

Practice

1. What does vertical order traversal of a binary tree mean?

easy

A. Nodes are visited level by level from top to bottom

B. Nodes are visited in inorder (left, root, right)

C. Nodes are visited in preorder (root, left, right)

D. Nodes are grouped by their vertical columns from left to right

Solution

1. Step 1: Understand vertical order traversal concept

   Vertical order traversal groups nodes by their vertical columns, where nodes in the same vertical line share the same horizontal distance from the root.

2. Step 2: Compare with other traversals

   Level order visits nodes by depth, preorder and inorder are depth-first traversals, not grouped by vertical columns.

3. Final Answer:

   Nodes are grouped by their vertical columns from left to right -> Option D

4. Quick Check:

   Vertical order = group by vertical columns [OK]

Hint: Vertical order groups nodes by vertical columns [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking preorder or inorder is vertical order
• Ignoring horizontal distance concept

2. Which C++ data structure is best suited to store nodes grouped by their vertical columns during vertical order traversal?

easy

A. std::vector<int>

B. std::queue<int>

C. std::map

D. std::stack<int>

Solution

1. Step 1: Identify need to group nodes by vertical column

   We need a structure that maps vertical column indices (integers) to lists of node values.

2. Step 2: Choose appropriate C++ container

   std::map maps column indices to vectors of node values, maintaining sorted order of columns automatically.

3. Final Answer:

   std::map -> Option C

4. Quick Check:

   Map column index to node list = std::map [OK]

Hint: Use map to group nodes by column [OK]

Common Mistakes:

• Using vector alone loses column indexing
• Stack or queue do not map keys to values
• Using unordered_map loses column order

3. Given the binary tree:

    1
   / \
  2   3
 /     \
4       5

What is the vertical order traversal output?

medium

A. [4, 2, 1, 3, 5]

B. [4, 2, 1, 5, 3]

C. [1, 2, 3, 4, 5]

D. [2, 4, 1, 3, 5]

Solution

1. Step 1: Assign horizontal distances (HD) to nodes

   Root 1 has HD=0; left child 2 has HD=-1; right child 3 has HD=1; 4 is left of 2 so HD=-2; 5 is right of 3 so HD=2.

2. Step 2: Group nodes by HD and list in order

   HD=-2: [4], HD=-1: [2], HD=0: [1], HD=1: [3], HD=2: [5]. Combine left to right: [4, 2, 1, 3, 5].

3. Final Answer:

   [4, 2, 1, 3, 5] -> Option A

4. Quick Check:

   Vertical order = [4, 2, 1, 3, 5] [OK]

Hint: Assign horizontal distances, then list nodes left to right [OK]

Common Mistakes:

• Mixing order of nodes in same vertical column
• Ignoring horizontal distance for children
• Listing nodes by level order instead

4. Consider this code snippet for vertical order traversal:

void verticalOrder(Node* root) {
  map m;
  queue> q;
  q.push({root, 0});
  while (!q.empty()) {
    auto p = q.front(); q.pop();
    Node* node = p.first;
    int hd = p.second;
    m[hd].push_back(node->data);
    if (node->left) q.push({node->left, hd - 1});
    if (node->right) q.push({node->right, hd + 1});
  }
  for (auto &x : m) {
    for (int val : x.second) cout << val << " ";
  }
}

What is the bug in this code?

medium

A. It does not handle empty tree (root == nullptr)

B. It uses map instead of unordered_map causing wrong order

C. It pushes right child before left child in queue

D. It does not store horizontal distances correctly

Solution

1. Step 1: Check for null root before processing

   The code assumes root is not null but does not check. If root is nullptr, q.push({root, 0}) pushes null pointer causing runtime error.

2. Step 2: Verify other parts are correct

   Using map keeps columns sorted, order of pushing left then right is correct, horizontal distances are updated properly.

3. Final Answer:

   It does not handle empty tree (root == nullptr) -> Option A

4. Quick Check:

   Missing null root check causes error [OK]

Hint: Always check if root is nullptr before traversal [OK]

Common Mistakes:

• Ignoring null root causing crash
• Confusing map with unordered_map for order
• Swapping left and right child pushes

5. You want to modify vertical order traversal to print nodes sorted by their depth within each vertical column (top to bottom). Which data structure change helps achieve this?

hard

A. Use map and sort vectors after traversal

B. Use map> to store nodes by column and depth

C. Use unordered_map and sort keys later

D. Use queue> only without map

Solution

1. Step 1: Understand requirement to sort nodes by depth per column

   We need to group nodes by vertical column and also by their depth (level) to print top to bottom.

2. Step 2: Choose data structure to store nodes by column and depth

   Using map> allows mapping column -> depth -> list of nodes, preserving order in both dimensions.

3. Final Answer:

   Use map> to store nodes by column and depth -> Option B

4. Quick Check:

   Nested map for column and depth sorting [OK]

Hint: Use nested map to sort nodes by column and depth [OK]

Common Mistakes:

• Sorting vectors after traversal is inefficient
• Using unordered_map loses order
• Ignoring depth dimension in grouping