Print a Binary Tree in Vertical Order

Print a Binary Tree in Vertical Order | Set 1

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 

-------------------------- thinking --------------------------
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
------------------------ codes --------------------------

struct my_pair{

    TreeNode *node;

    int       hd;

    my_pair(TreeNode *n, int d): node(n), hd(d){}

};

class Solution {

public:

    vector<vector<int>> printVirtical(TreeNode *root){

        // write your code here

        int start = 0;

        int end = 0;

        findMinMax(root, 0, start, end);

        vector<vector<int>> result(end-start+1, vector<int>());

        queue<my_pair> que;

        if (root == NULL) return result;

        my_pair pair(root, 0);

        que.push(pair);

        while (!que.empty()) {

            my_pair cur = que.front();

            que.pop();

            result[cur.hd - start].push_back(cur.node->val);

            if (cur.node->left) {

                my_pair pair(cur.node->left, cur.hd-1);

                que.push(pair);

            }

            if (cur.node->right) {

                my_pair pair(cur.node->right, cur.hd+1);

                que.push(pair);

            }

        }

        return result;

    }

    void findMinMax(TreeNode *root, int hd, int &start, int &end) {

        if (root->left) {

            if (start > hd - 1) {

                start = hd - 1;

            }

            findMinMax(root->left, hd - 1, start, end);

        }

        if (root->right) {

            if (end < hd + 1) {

                end = hd + 1;

            }

            findMinMax(root->right, hd + 1, start, end);

        }

    }

};