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.