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;
}