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:
- Map
- Horizontal Distance
- 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:
- For root node, horizontal distance = 0.
- For left node, horizontal distance = parent horizontal distance – 1
- 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