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.