Vertical Order Traversal of Binary Tree in DSA C

Mental Model

We group tree nodes by their vertical columns and print nodes column by column from left to right.

Analogy: Imagine standing in front of a tree and looking straight at it. Nodes that line up vertically in your view belong to the same column.

       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: Print nodes grouped by vertical columns from left to right

Step 1: Start at root node 1 with column 0

Column 0: [1]

Why: Root is the center column

Step 2: Move to left child 2 with column -1

Column -1: [2]
Column 0: [1]

Why: Left child is one column left

Step 3: Move to left child 4 with column -2

Column -2: [4]
Column -1: [2]
Column 0: [1]

Why: Left child again moves one column left

Step 4: Back to 2, move to right child 5 with column 0

Column -2: [4]
Column -1: [2]
Column 0: [1,5]

Why: Right child moves one column right

Step 5: Back to root 1, move to right child 3 with column 1

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

Why: Right child moves one column right

Step 6: Move to right child 6 of 3 with column 2

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

Why: Right child moves one column right

Result:

4
2
1 5
3
6

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Tree node structure
typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

// Queue node for BFS traversal
typedef struct QNode {
    Node* treeNode;
    int col;
    struct QNode* next;
} QNode;

// Queue structure
typedef struct Queue {
    QNode* front;
    QNode* rear;
} Queue;

// Map node for storing column to list of values
typedef struct MapNode {
    int col;
    int* values;
    int size;
    int capacity;
    struct MapNode* next;
} MapNode;

// Map structure (linked list for simplicity)
typedef struct Map {
    MapNode* head;
} Map;

// Create new tree node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Initialize queue
void initQueue(Queue* q) {
    q->front = NULL;
    q->rear = NULL;
}

// Enqueue tree node with column
void enqueue(Queue* q, Node* node, int col) {
    QNode* qnode = (QNode*)malloc(sizeof(QNode));
    qnode->treeNode = node;
    qnode->col = col;
    qnode->next = NULL;
    if (q->rear == NULL) {
        q->front = qnode;
        q->rear = qnode;
    } else {
        q->rear->next = qnode;
        q->rear = qnode;
    }
}

// Dequeue
QNode* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    QNode* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    return temp;
}

// Initialize map
void initMap(Map* map) {
    map->head = NULL;
}

// Find or create map node for column
MapNode* getMapNode(Map* map, int col) {
    MapNode* curr = map->head;
    while (curr != NULL) {
        if (curr->col == col) return curr;
        curr = curr->next;
    }
    // Not found, create new
    MapNode* new_map_node = (MapNode*)malloc(sizeof(MapNode));
    new_map_node->col = col;
    new_map_node->size = 0;
    new_map_node->capacity = 4;
    new_map_node->values = (int*)malloc(sizeof(int) * new_map_node->capacity);
    new_map_node->next = map->head;
    map->head = new_map_node;
    return new_map_node;
}

// Add value to map node
void addValue(MapNode* mapNode, int val) {
    if (mapNode->size == mapNode->capacity) {
        mapNode->capacity *= 2;
        mapNode->values = (int*)realloc(mapNode->values, sizeof(int) * mapNode->capacity);
    }
    mapNode->values[mapNode->size++] = val;
}

// Compare function for qsort to sort map nodes by column
int cmpMapNode(const void* a, const void* b) {
    MapNode* m1 = *(MapNode**)a;
    MapNode* m2 = *(MapNode**)b;
    return m1->col - m2->col;
}

// Vertical order traversal function
void verticalOrderTraversal(Node* root) {
    if (root == NULL) return;
    Queue q;
    initQueue(&q);
    Map map;
    initMap(&map);

    enqueue(&q, root, 0);

    while (q.front != NULL) {
        QNode* qnode = dequeue(&q);
        Node* curr = qnode->treeNode;
        int col = qnode->col;
        free(qnode);

        MapNode* mapNode = getMapNode(&map, col);
        addValue(mapNode, curr->val);

        if (curr->left != NULL) enqueue(&q, curr->left, col - 1);
        if (curr->right != NULL) enqueue(&q, curr->right, col + 1);
    }

    // Count map nodes
    int count = 0;
    MapNode* curr = map.head;
    while (curr != NULL) {
        count++;
        curr = curr->next;
    }

    // Collect map nodes into array for sorting
    MapNode** arr = (MapNode**)malloc(sizeof(MapNode*) * count);
    curr = map.head;
    for (int i = 0; i < count; i++) {
        arr[i] = curr;
        curr = curr->next;
    }

    qsort(arr, count, sizeof(MapNode*), cmpMapNode);

    // Print values column by column
    for (int i = 0; i < count; i++) {
        for (int j = 0; j < arr[i]->size; j++) {
            printf("%d", arr[i]->values[j]);
            if (j < arr[i]->size - 1) printf(" ");
        }
        printf("\n");
    }

    free(arr);
}

int main() {
    // Build tree from dry run example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(6);

    verticalOrderTraversal(root);
    return 0;
}

enqueue(&q, root, 0);

Start BFS with root at column 0

QNode* qnode = dequeue(&q);

Remove front node from queue to process

MapNode* mapNode = getMapNode(&map, col);

Find or create map entry for current column

addValue(mapNode, curr->val);

Add current node's value to its column group

if (curr->left != NULL) enqueue(&q, curr->left, col - 1);

Add left child to queue with column one less

if (curr->right != NULL) enqueue(&q, curr->right, col + 1);

Add right child to queue with column one more

qsort(arr, count, sizeof(MapNode*), cmpMapNode);

Sort columns from left to right

printf("%d", arr[i]->values[j]);

Print all nodes in current column

Output

4

2

1 5

3

6

Complexity Analysis

Time: O(n log n) because we visit all n nodes once and then sort columns which can be up to n

Space: O(n) because we store all nodes in the map and queue

vs Alternative: Naive approach might do multiple traversals or use extra sorting per node, increasing time; this BFS with map and sorting columns is efficient

Edge Cases

Empty tree

No output, function returns immediately

DSA C

if (root == NULL) return;

Tree with single node

Prints single node value in one column

DSA C

enqueue(&q, root, 0);

Tree with all nodes in one vertical column

All nodes printed in one line in order of BFS

DSA C

addValue(mapNode, curr->val);

When to Use This Pattern

When you need to print or group tree nodes by their vertical alignment, use vertical order traversal with BFS and column indexing.

Common Mistakes

Mistake: Not tracking column indices correctly when moving left or right
Fix: Always decrement column by 1 when moving left and increment by 1 when moving right

Mistake: Not sorting columns before printing
Fix: Collect all columns and sort them by their column index before output

Summary

Groups and prints tree nodes by their vertical columns from left to right.

Use when you want to see nodes aligned vertically in a binary tree.

Track column indices during BFS and group nodes by these indices.

Practice

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

easy

A. Nodes grouped by their vertical columns from left to right

B. Nodes grouped by their depth levels from top to bottom

C. Nodes visited in preorder traversal order

D. Nodes visited in postorder traversal order

Solution

1. Step 1: Understand vertical order traversal concept

   Vertical order traversal groups nodes by their vertical columns, where the root is at column 0, left child at column -1, right child at column +1, and so on.

2. Step 2: Compare with other traversal types

   Depth levels group nodes horizontally, preorder and postorder are depth-first traversals, not vertical grouping.

3. Final Answer:

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

4. Quick Check:

   Vertical order = vertical columns grouping [OK]

Hint: Vertical order groups nodes by columns, not levels or order [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking preorder or postorder is vertical order
• Mixing horizontal levels with vertical columns

2. Which data structure is commonly used to store nodes during vertical order traversal?

easy

A. Queue

B. HashMap or Dictionary

C. Stack

D. Linked List

Solution

1. Step 1: Identify storage needs for vertical order traversal

   We need to group nodes by their vertical column index, so a map (like HashMap or Dictionary) is used to store lists of nodes per column.

2. Step 2: Understand role of other data structures

   Queue is used for level order traversal but not for grouping columns; stack and linked list do not directly map columns to nodes.

3. Final Answer:

   HashMap or Dictionary -> Option B

4. Quick Check:

   Use map to group nodes by column [OK]

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

Common Mistakes:

• Using stack instead of map for grouping
• Confusing queue usage for traversal with storage
• Not grouping nodes by column properly

3. What is the output of vertical order traversal for this tree?

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Assign vertical columns to each node

   Root 1 is at column 0; 2 is at -1; 3 is at +1; 4 is at -2; 5 is at 0; 6 is at +2.

2. Step 2: Group nodes by columns and read left to right

   Column -2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]. Reading in order: 4, 2, 1, 5, 3, 6.

3. Final Answer:

   [4, 2, 1, 5, 3, 6] -> Option D

4. Quick Check:

   Group by columns left to right [OK]

Hint: Assign columns: left -1, right +1; group and read left to right [OK]

Common Mistakes:

• Mixing order of nodes in same column
• Ignoring multiple nodes in one column
• Reading nodes top-down instead of column-wise

4. Identify the error in this vertical order traversal code snippet:

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

medium

A. Not sorting nodes inside each column before printing

B. Using map instead of unordered_map causes slower performance

C. Missing check if root is NULL before pushing to queue

D. Incorrect decrement and increment of column index for children

Solution

1. Step 1: Check initial queue push

   The code pushes root to queue without checking if root is NULL, which can cause runtime error if tree is empty.

2. Step 2: Verify other parts

   Column indices are correctly updated; map usage is valid; sorting nodes inside columns is optional depending on problem.

3. Final Answer:

   Missing check if root is NULL before pushing to queue -> Option C

4. Quick Check:

   Always check root != NULL before queue push [OK]

Hint: Check root != NULL before queue push to avoid errors [OK]

Common Mistakes:

• Ignoring NULL root causing crash
• Thinking map usage is incorrect
• Assuming sorting inside columns is mandatory

5. Given a binary tree, how would you modify vertical order traversal to print nodes sorted by their row (depth) within each vertical column?

hard

A. Store nodes in map>> with (row, value) and sort by row before printing

B. Use a stack instead of queue to traverse nodes depth-first

C. Ignore row and print nodes in order they appear in queue

D. Use unordered_map and sort keys before printing

Solution

1. Step 1: Understand requirement to sort by row within columns

   We need to track both column and row (depth) for each node to sort nodes vertically and then by depth.

2. Step 2: Use map with pairs and sort

   Store nodes in map keyed by column with vector of (row, value) pairs. Sort vector by row before printing to get correct order.

3. Final Answer:

   Store nodes in map<int, vector<pair<int,int>>> with (row, value) and sort by row before printing -> Option A

4. Quick Check:

   Track row and column, sort by row inside columns [OK]

Hint: Track row with column, sort nodes by row inside each column [OK]

Common Mistakes:

• Not tracking row, so nodes unordered by depth
• Using stack breaks level order needed for row tracking
• Ignoring sorting inside columns