ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Vertical Order Traversal

prodevelopertutorial March 30, 2020

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:

 

Vertical Order Traversal

 

The vertical order traversal can be visualized as below:

Vertical Order Traversal

 

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:

 

Vertical Order Traversal

 

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:

 

Vertical Order Traversal

 

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:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io