Vertical Order Traversal

In this tutorial we shall see how to do vertical order traversal.

Problem Statement:

You are given a root node of a tree, you need to print the nodes when they are traversed vertically.

Consider the tree given below:

The vertical order traversal can be visualized as below:

So the vertical order traversal will be:

d

b

a e f

c

g

So how can we arrive at this result?

We can arrive at the result with the help of:

1. Map
2. Horizontal Distance
3. Level Order Traversal

We shall see how all these 3 takes part in arriving at the solution.

First how to calculate horizontal distance?

We can calculate horizontal distance by below steps:

1. For root node, horizontal distance = 0.
2. For left node, horizontal distance = parent horizontal distance – 1
3. For right node, horizontal distance = parent horizontal distance + 1

Now, let’s calculate horizontal distance for all the nodes.

As “a” is root node, it’s distance is 0.

b = 0 – 1 = -1

d = -1 – 1 = -2

c = 0 + 1 = 1

g = 1 + 1 = 2

e = -1 + 1 = 0

f = 1 – 1 = 0

Finally, the horizontal distance will look like below:

Now in the hash map, sort the horizontal distance value according to ascending order. Then insert the nodes according to their Horizontal Distance [HD] value.

The hash map will look like below:

Now a question arises. Why we inserted “a, e, f” in that order?

We added it with the help of level order traversal. When we do level order traversal, we get those 3 nodes in that order.

We get our result.

Solution in C++

#include <iostream>
#include <vector>
#include <map>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

void perform_vertical_order_traversal(Node *root, map<int,vector<int>>& map, int h_dist)
{
  // Base case
  if (root == NULL)
    return;

    map[h_dist].push_back(root -> data);

  perform_vertical_order_traversal(root -> left, map, h_dist - 1);
  perform_vertical_order_traversal(root -> right, map, h_dist + 1);
}


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    map<int,vector<int>> myMap;

    perform_vertical_order_traversal(root, myMap, 0);

    cout<<"The vertical order traversal is"<< endl;

    for (auto it = myMap.begin(); it != myMap.end(); ++it)
    {
        for (int i=0; i< it->second.size(); ++i) 
            cout << it->second[i] << " "; 
        cout << endl;     }
    return 0;  
}

Output:

7
10
16 15 18
25
30

List Of Tutorials available in this website: