Vertical Order Traversal of Binary Tree in DSA C - Build from Scratch

Vertical Order Traversal of Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to see the family members grouped by their vertical positions when you look at the tree from the front.

🎯 Goal: Build a program in C that performs vertical order traversal of a binary tree and prints the nodes grouped by their vertical columns from left to right.

📋 What You'll Learn

Create a binary tree with the exact structure given

Use a variable to track the horizontal distance (column) of nodes

Implement vertical order traversal logic using a queue and a map-like structure

Print the nodes grouped by their vertical columns in order

💡 Why This Matters

🌍 Real World

Vertical order traversal helps visualize hierarchical data like family trees, organizational charts, or layered maps from a vertical perspective.

💼 Career

Understanding tree traversals and queue usage is essential for software engineering roles involving data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Define a struct called Node with int data, Node *left, and Node *right. Then create nodes to build this exact tree:

1
/ \
2 3
/ \ \
4 5 6

DSA C

// Define struct Node and create the binary tree nodes
// Your code here

Hint

Start by defining the Node struct and a helper function newNode to create nodes. Then build the tree exactly as shown.

2

Set Up Data Structures for Vertical Traversal

Create a struct called QueueNode with Node *node and int hd (horizontal distance). Then create a queue using an array of QueueNode with size 100. Also create an integer array columnTable[201] initialized to 0 to store sums of nodes at each horizontal distance shifted by 100.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    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);

    // Define QueueNode struct and queue array
    // Your code here

    return 0;
}

Hint

Create a QueueNode struct to hold a tree node and its horizontal distance. Then create a queue array and an integer array columnTable to store sums indexed by horizontal distance + 100.

3

Implement Vertical Order Traversal Logic

Use a while loop to perform level order traversal with the queue. Enqueue the root with horizontal distance 100. While queue is not empty, dequeue a QueueNode, add its node's data to columnTable[hd]. Enqueue left child with hd - 1 and right child with hd + 1 if they exist.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

typedef struct QueueNode {
    Node* node;
    int hd;
} QueueNode;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    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);

    QueueNode queue[100];
    int front = 0, rear = 0;
    int columnTable[201] = {0};

    // Enqueue root with hd 100
    // Use while loop to process queue
    // Your code here

    return 0;
}

Hint

Start by enqueuing the root with horizontal distance 100. Then use a while loop to dequeue nodes, add their data to columnTable, and enqueue their children with updated horizontal distances.

4

Print the Vertical Order Traversal Result

Use a for loop from i = 0 to 200. If columnTable[i] is not zero, print the value followed by a space. This will print the sum of nodes in each vertical column from left to right.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

typedef struct QueueNode {
    Node* node;
    int hd;
} QueueNode;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    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);

    QueueNode queue[100];
    int front = 0, rear = 0;
    int columnTable[201] = {0};

    queue[rear].node = root;
    queue[rear].hd = 100;
    rear++;

    while (front data;

        if (currNode->left != NULL) {
            queue[rear].node = currNode->left;
            queue[rear].hd = hd - 1;
            rear++;
        }
        if (currNode->right != NULL) {
            queue[rear].node = currNode->right;
            queue[rear].hd = hd + 1;
            rear++;
        }
    }

    // Print the vertical order sums
    // Your code here

    return 0;
}

Hint

Loop through columnTable and print all non-zero sums separated by spaces. This shows the vertical order sums from left to right.

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