I'm trying to solve the problem of Vertical Order Traversal of Binary Tree using map and queue. I did solve it using a recursive way, but I'm not getting the same answer using the iterative way.
10
/ \
7 4
/ \ / \
3 11 14 6
Approach :
First I declared an integer that stores horizontal distance from the root node.
Horizontal distance means that the left part from the root will be considered as -1, -2 and so on, like a negative X axis, where the root is origin and starts from 0. So node 7 will be given -1, 3 will be given -2. However, 10, 11, 14 will be given 0 as they are not away from root node but lie in the same position. And towards the right, distance will become positive so 4 will get distance 1, 6 will get 2 and so on.
At first, I pushed the root in the queue and updated the horizontal distance as 0. After that, I added horizontal distance as key and root data as value in the map. And finally, I poped the root from the queue and I checked for its left and right child, if left or right child was available, I pushed the left and right child in the queue respectively and updated horizontal distance accordingly. Then I followed the same procedure for the complete binary tree.
And then, I just traversed through the second part of the map to get the answer.
The Answer should be :
3
7
10 11 14
4
6
The Answer I received is :
10 7 4 3 11 14 6
Here is my Code :
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
Node(int val)
{
data = val;
left = NULL;
right = NULL;
}
};
map<int, vector<int>> verticalPrint(Node *root)
{
queue<Node *> qi;
map<int, vector<int>> mp;
int Hd = 0;
qi.push(root);
while (!qi.empty())
{
Node *temp = qi.front();
mp[Hd].push_back(temp->data);
qi.pop();
if (temp->left != NULL)
{
qi.push(temp->left);
Hd -= 1;
}
if (temp->right != NULL)
{
qi.push(temp->right);
Hd += 1;
}
}
return mp;
}
int main()
{
Node *root = new Node(10);
root->left = new Node(7);
root->right = new Node(4);
root->left->left = new Node(3);
root->left->right = new Node(11);
root->right->left = new Node(14);
root->right->right = new Node(6);
map<int, vector<int>> mp = verticalPrint(root);
map<int, vector<int>>::iterator it;
for (it = mp.begin(); it != mp.end(); it++)
{
for (int i = 0; i < it->second.size(); i++)
{
cout << it->second[i] << " ";
}
cout << endl;
}
return 0;
}