Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate.  Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note:

1. The tree will have between 1 and 1000 nodes.
2. Each node's value will be between 0 and 1000.

 ===================== Pre order traversal is not the right approach here =======

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if (root == NULL) {
            return vector<vector<int>>();
        }
        vector<vector<int>> ans;
        map<int, vector<int>> mp;
        helper(root, 0, mp);
        generate(mp, ans);
        return ans;
    }
 
    void helper(TreeNode* root, int location, map<int, vector<int>>& mp) {
        if (root == NULL) {
            return;
        }
        mp[location].push_back(root -> val);
        helper(root -> left, location - 1, mp);
        helper(root -> right, location + 1, mp);
        return;
    }
 
    void generate(map<int, vector<int>>& mp, vector<vector<int>>& ans) {
        map<int, vector<int>>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++) {
            ans.push_back(it -> second);
        }
        return;
    }
};


========== . Queue is not working as well =====

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if (root == NULL) {
            return vector<vector<int>>();
        }
        vector<vector<int>> ans;
        map<int, vector<int>> mp;
        helper(root, 0, mp);
        generate(mp, ans);
        return ans;
    }
 
    void helper(TreeNode* root, int location, map<int, vector<int>>& mp) {
        if (root == NULL) {
            return;
        }
        queue<pair<int, TreeNode*>> q;
        q.push(make_pair(0, root));
     
        while (!q.empty()) {
            pair<int, TreeNode*> node = q.front(); q.pop();
            mp[node.first].push_back(node.second -> val);
            if (node.second -> left) {
                q.push(make_pair(node.first - 1, node.second -> left));
            }
            if (node.second -> right) {
                q.push(make_pair(node.first + 1, node.second -> right));
            }
        }
    }
 
    void generate(map<int, vector<int>>& mp, vector<vector<int>>& ans) {
        map<int, vector<int>>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++) {
            ans.push_back(it -> second);
        }
        return;
    }
};

================== Right one ============
class Solution
{
    public:
    vector<vector<int>> verticalTraversal(TreeNode* root)
    {
        vector<vector<int>> result;
        map<int,map<int,vector<int>>> total;
        deque<TreeNode*> q;
        deque<int> p;
        deque<int> h;
        q.push_back(root);
        p.push_back(0);
        h.push_back(0);
        while(q.size()>0)
        {
            TreeNode* c=q.front();
            int x=p.front();
            int y=h.front();
            q.pop_front();
            p.pop_front();
            h.pop_front();
            total[x][y].push_back(c->val);
            if(c->left!=NULL)
            {
                q.push_back(c->left);
                p.push_back(x-1);
                h.push_back(y+1);
            }
            if(c->right!=NULL)
            {
                q.push_back(c->right);
                p.push_back(x+1);
                h.push_back(y+1);
            }
        }
        for(map<int,map<int,vector<int>>>::iterator it1=total.begin();it1!=total.end();it1++)
        {
            vector<int> temp;
            for(map<int,vector<int>>::iterator it2=it1->second.begin();it2!=it1->second.end();it2++)
            {
                sort(it2->second.begin(),it2->second.end());
                for(int i=0;i<it2->second.size();i++)
                {
                    temp.push_back(it2->second[i]);
                }
            }
            result.push_back(temp);
        }
        return result;
    }
};