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 side.

🎯 Goal: You will build a program in C++ that performs a vertical order traversal of a binary tree. This means grouping nodes that appear in the same vertical line and printing them from left to right.

📋 What You'll Learn

Create a binary tree with given nodes

Use a map to group nodes by their vertical column index

Traverse the tree using a breadth-first search (BFS) approach

Print the nodes grouped by their vertical order

💡 Why This Matters

🌍 Real World

Vertical order traversal helps visualize hierarchical data from a side view, useful in graphical layouts and family trees.

💼 Career

Understanding tree traversals and using maps and queues is essential for software engineering roles involving data structures and algorithms.

1

Create the Binary Tree Structure and Nodes

Define a struct called Node with an int data, and two pointers left and right. Then create the root node with value 1, its left child with value 2, and right child with value 3. Also create left child of node 2 with value 4 and right child of node 2 with value 5.

DSA C++

#include 
using namespace std;

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

Hint

Start by defining the Node structure with a constructor. Then create the root and its children exactly as described.

2

Setup Data Structures for Vertical Order Traversal

Include the headers <map>, <queue>, and <vector>. Declare a map<int, vector<int>> called verticalMap to store nodes by their vertical column. Also declare a queue<pair<Node*, int>> called q to hold nodes and their column indices.

DSA C++

#include 
#include 
#include 
#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

    // Declare verticalMap and queue q
    // Your code here

    return 0;
}

Hint

Include the necessary headers and declare the map and queue variables exactly as described.

3

Perform Vertical Order Traversal Using BFS

Push the root node with column 0 into the queue q. Use a while loop to process nodes until q is empty. In each iteration, pop the front node and its column index. Append the node's data to verticalMap[column]. If the node has a left child, push it with column - 1. If the node has a right child, push it with column + 1.

DSA C++

#include 
#include 
#include 
#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

    map> verticalMap;
    queue> q;

    // Push root with column 0 and traverse
    // Your code here

    return 0;
}

Hint

Use a queue to do a breadth-first traversal. Track each node's column index and add its data to the map. Push children with updated column indices.

4

Print the Vertical Order Traversal Result

Use a for loop to iterate over verticalMap. For each column, print the node values separated by spaces. Print a newline after each column.

DSA C++

#include 
#include 
#include 
#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

    map> verticalMap;
    queue> q;

    q.push({root, 0});
    while (!q.empty()) {
        auto front = q.front();
        q.pop();
        Node* node = front.first;
        int col = front.second;
        verticalMap[col].push_back(node->data);
        if (node->left) {
            q.push({node->left, col - 1});
        }
        if (node->right) {
            q.push({node->right, col + 1});
        }
    }

    // Print vertical order traversal
    // Your code here

    return 0;
}

Hint

Loop through the map and print each vector of node values separated by spaces. Print a newline after each column.

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