Given a binary tree, print it vertically. The following example illustrates vertical order traversal.
1
/ \
2 3
/ \ / \
4 5 6 7
\ \
8 9
The output of print this tree vertically will be: 4 2 1 5 6 3 8 7 9
#include <iostream>
#include <vector>
#include <map>
#include <cstdlib>
using namespace std;
struct Node {
int key;
Node* left;
Node* right;
};
struct Node* newNode(int key)
{
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->key = key;
node->left = node->right = NULL;
return node;
}
void getVerticalOrder(Node* root,int verticalLevel,map< int,vector<int> >& m) {
if(!root) return;
m[verticalLevel].push_back(root->key);
getVerticalOrder(root->left,verticalLevel-1,m);
getVerticalOrder(root->right,verticalLevel+1,m);
}
void printVerticalOrder(Node* root) {
map < int,vector<int> > m;
int verticalLevel = 0;
getVerticalOrder(root,verticalLevel,m);
map< int,vector<int> > :: iterator it;
for(it=m.begin();it!=m.end();it++) {
for(int i=0;i<it->second.size();++i) {
cout<<it->second[i]<<" ";
}
cout<<endl;
}
}
int main() {
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->right = newNode(8);
root->right->right->right = newNode(9);
cout << "Vertical order traversal is \n";
printVerticalOrder(root);
return 0;
}
