Vertical Traversal of Binary Tree
“Vertical Traversal of Binary Tree” is one of the foremost algorithmic problem based on tree data structure asked in technical interview. Here, we are given a binary tree and our task is to traverse the given binary tree vertically.
For vertical order traversal, we need to calculate Horizontal Distance (HD) for each node of given binary tree. Horizontal Distance in case of Binary Tree is defined as distance of node from root node. Horizontal Distance of Root Node is always considered as 0, then right child node will have HD as +1 and left child node will have HD as -1. If two nodes have same horizontal distance, then they are considered to be on same vertical Line.
There can be varied ways to traverse the binary tree vertically. Here, in this post we are going to discuss two methods to implement the Vertical Binary Tree Traversal.
- Preorder Traversal with Hashing
- Level Order Traversal with Hashing
METHOD 1: Preorder Traversal with Hashing
Here, we can recursively calculate Horizontal distance of each node and insert the node into HashMap accordingly.
The steps required to implement Vertical Traversal of Binary Tree are as follows:
- Create a HashMap to store Vertical Order and node value.
- For root, initialize HD = 0.
- Recursively perform following steps:
- Check and return from Base Case.
- Store the current node into map according to its HD.
- Recursively Call the function for left subtree by passing current HD – 1.
- Recursively Call the function for right subtree by passing current HD + 1.
- Print the Vertical traversal stored in HashMap.
C++ Program to implement Vertical Traversal of Binary Tree is as follows:
/* C++ Program to implement vertical traversal of Binary Tree */
#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;
/* Function to insert node values in hashmap according to horizontal distances */
void verticalTraversalRecurr(Node *root, int HD, map<int, vector<int>> &mp)
{
/* Base Case */
if(root == NULL)
return;
/* Store Current Node into Map */
mp[HD].push_back(root -> data);
/* Recursively Call for left subtree by updating HD-1 */
verticalTraversalRecurr(root -> left, HD-1, mp);
/* Recursively Call for right subtree by updating HD+1 */
verticalTraversalRecurr(root -> right, HD+1, mp);
}
/* Function to Implement Vertical Traversal of Binary Tree */
void verticalTraversal(Node *root)
{
/* Base Case */
if(root == NULL)
return;
map<int, vector<int>> mp;
int hd = 0;
verticalTraversalRecurr(root, hd, mp);
/* Print the Vertical Traversal, stored in HashMap */
map <int, vector<int>> :: iterator itr;
for(itr = mp.begin(); itr != mp.end(); ++itr)
{
for(int i = 0; i < itr -> second.size(); i++)
cout << itr->second[i] << " ";
cout<<endl;
}
}
int main()
{
/* Creating a Binary tree and inserting some nodes in it */
Node *root = NULL;
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);
root -> right -> left = new Node(6);
root -> right -> right = new Node (7);
root -> left -> right -> left = new Node(8);
root -> right -> left -> right = new Node(9);
/* Calling function to perform vertical traversal*/
cout<<"The Veritcal Traversal of the Given Binary Tree is:\n";
verticalTraversal(root);
}
OUTPUT:
The Veritcal Traversal of the Given Binary Tree is: 4 2 8 1 5 6 3 9 7
METHOD 2: Level Order Traversal using Hashing
Here, we are going modify the queue used in Level order traversal to store both node and corresponding horizontal distance of each node. Also, we need to create a map which store the vertical order line of tree.
The steps required to implement Vertical Traversal of Binary Tree are as follows:
- Create a map which store the vertical order and corresponding nodes.
- Create a queue which can store node and corresponding HD and push root node with corresponding distance as 0.
- Perform following steps until queue is not empty:
- Pop the element from queue and store it in the map according to vertical order.
- If the popped node has left child, push it into queue and pass HD as current (HD-1).
- If popped node has right child push it into queue and pass HD as current (HD+1).
- Display the data of map which stores the vertical order traversal of given binary tree.
C++ Program to implement Vertical Traversal of Binary Tree is as follows:
/* C++ Program to implement vertical traversal of Binary Tree */
#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;
/* Function to Implement Vertical Traversal of Binary Tree */
void verticalTraversal(Node *root)
{
/* Base Case */
if(root == NULL)
return;
/*
Create a map which store the vertical order traversal,
"int" refers to store the vertical line number
"vector<int>" refers to the chained node values lying on verical line
*/
map <int, vector<int>> mp;
int hd = 0;
/*
Create Queue and every element of queue will store
node and corresponding Horizontal Distance
*/
queue<pair<Node*, int>> que;
que.push(make_pair(root,hd));
while(!que.empty())
{
/* Pop Front Element from queue */
pair<Node*, int> temp = que.front();
que.pop();
hd = temp.second;
Node *temp_node = temp.first;
/* Push the Node into map according to vertical order line */
mp[hd].push_back(temp_node -> data);
if(temp_node -> left)
que.push(make_pair(temp_node -> left, hd - 1));
if(temp_node -> right)
que.push(make_pair(temp_node -> right, hd + 1));
}
/* Print map ehich holds vertical order traversal */
map<int, vector<int>> :: iterator itr;
for(itr = mp.begin(); itr != mp.end(); ++itr)
{
for(int i = 0; i < itr->second.size(); i++)
{
cout << itr -> second[i] << " ";
}
cout<<endl;
}
}
int main()
{
/* Creating a Binary tree and inserting some nodes in it */
Node *root = NULL;
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);
root -> right -> left = new Node(6);
root -> right -> right = new Node (7);
root -> left -> right -> left = new Node(8);
root -> right -> left -> right = new Node(9);
/* Calling function to perform vertical traversal*/
cout<<"The Veritcal Traversal of the Given Binary Tree is:\n";
verticalTraversal(root);
}
OUTPUT:
The Veritcal Traversal of the Given Binary Tree is: 4 2 8 1 5 6 3 9 7
Related Posts:
- Introduction to Tree Data Structure
- Binary Tree Traversals
- Print All Leaf Nodes of a Binary Tree
- Count Number of Nodes in a Binary Tree
- Print Alternate Levels of Binary Tree
- Maximum Width of Binary Tree
- Level Order Tree Traversal
- Left View of Binary Tree
- Right View of Binary Tree
- Compute Height of Binary Tree
- Inorder Tree Traversal Using Stack
- Preorder Tree Trasversal Using Stack
- Postorder Tree Traversal Using Stack
- Top View of Binary Tree
- Bottom View of Binary Tree
- Delete Complete Binary Tree
- Check if two trees are mirror Trees of Each Other
- Convert Binary Tree to its Mirror Tree
- Check if Binary Tree is Symmetric or Not
- Print All Root to Leaf Paths in a Binary Tree