<p>Given the <code>root</code> of a binary tree, calculate the <strong>vertical order traversal</strong> of the binary tree.</p>

<p>For each node at position <code>(row, col)</code>, its left and right children will be at positions <code>(row + 1, col - 1)</code> and <code>(row + 1, col + 1)</code> respectively. The root of the tree is at <code>(0, 0)</code>.</p>

<p>The <strong>vertical order traversal</strong> of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.</p>

<p>Return <em>the <strong>vertical order traversal</strong> of the binary tree</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/29/vtree1.jpg" style="width: 431px; height: 304px;" />
<pre>
<strong>Input:</strong> root = [3,9,20,null,null,15,7]
<strong>Output:</strong> [[9],[3,15],[20],[7]]
<strong>Explanation:</strong>
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/29/vtree2.jpg" style="width: 512px; height: 304px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,5,6,7]
<strong>Output:</strong> [[4],[2],[1,5,6],[3],[7]]
<strong>Explanation:</strong>
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
          1 is at the top, so it comes first.
          5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/29/vtree3.jpg" style="width: 512px; height: 304px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,6,5,7]
<strong>Output:</strong> [[4],[2],[1,5,6],[3],[7]]
<strong>Explanation:</strong>
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 1000]</code>.</li>
	<li><code>0 &lt;= Node.val &lt;= 1000</code></li>
</ul>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, map<int, multiset<int>>> mpp;
        queue<pair<TreeNode*, pair<int, int>>> q;
        q.push({root, {0, 0}});
        // int pre = INT_MIN;
        // int sc = 0;
        while(!q.empty()){
            TreeNode* n = q.front().first;
            int vl = q.front().second.first;
            int h = q.front().second.second;
            q.pop();
            mpp[vl][h].insert(n->val);

            if(n->left) q.push({n->left, {vl - 1, h + 1}});
            if(n->right) q.push({n->right, {vl + 1 , h + 1}});

        }
        vector<vector<int>> ans;
        for(auto it: mpp){
           vector<int> col;
           for(auto p : it.second){
            cout<<p.first<<endl;
            col.insert(col.end(), p.second.begin(), p.second.end());
           }
           cout<<'H'<<endl;
           ans.push_back(col);
           col.clear();
        }
        return ans;
        // Map to store nodes based on
        // vertical and level information
        // map<int, map<int, multiset<int>>> nodes;
        
        // // Queue for BFS traversal, each
        // // element is a pair containing node
        // // and its vertical and level information
        // queue<pair<TreeNode*, pair<int, int>>> todo;
        
        // // Push the root node with initial vertical
        // // and level values (0, 0)
        // todo.push({root, {0, 0}});
        
        // // BFS traversal
        // while(!todo.empty()){
        //     // Retrieve the node and its vertical
        //     // and level information from
        //     // the front of the queue
        //     auto p = todo.front();
        //     todo.pop();
        //     TreeNode* temp = p.first;
            
        //     // Extract the vertical and level information
        //     // x -> vertical
        //     int x = p.second.first;  
        //     // y -> level
        //     int y = p.second.second; 
            
        //     // Insert the node value into the
        //     // corresponding vertical and level
        //     // in the map
        //     nodes[x][y].insert(temp->val);
            
        //     // Process left child
        //     if(temp->left){
        //         todo.push({
        //             temp->left,
        //             {
        //                 // Move left in
        //                 // terms of vertical
        //                 x-1, 
        //                 // Move down in
        //                 // terms of level
        //                 y+1  
        //             }
        //         });
        //     }
            
        //     // Process right child
        //     if(temp->right){
        //         todo.push({
        //             temp->right, 
        //             {
        //                 // Move right in
        //                 // terms of vertical
        //                 x+1, 
        //                 // Move down in
        //                 // terms of level
        //                 y+1  
        //             }
        //         });
        //     }
        // }
        
        // // Prepare the final result vector
        // // by combining values from the map
        // vector<vector<int>> ans;
        // for(auto p: nodes){
        //     vector<int> col;
        //     for(auto q: p.second){
        //         // Insert node values
        //         // into the column vector
        //         col.insert(col.end(), q.second.begin(), q.second.end());
        //     }
        //     // Add the column vector
        //     // to the final result
        //     ans.push_back(col);
        // }
        // return ans;
    
    }
};


                            
// #include <iostream>
// #include <vector>
// #include <set>
// #include <queue>
// #include <map>

// using namespace std;

// // Node structure for the binary tree
// struct Node {
//     int data;
//     Node* left;
//     Node* right;
//     // Constructor to initialize
//     // the node with a value
//     Node(int val) : data(val), left(nullptr), right(nullptr) {}
// };

// class Solution {
// public:
//     // Function to perform vertical order traversal
//     // and return a 2D vector of node values
//     vector<vector<int>> findVertical(Node* root){
//         // Map to store nodes based on
//         // vertical and level information
//         map<int, map<int, multiset<int>>> nodes;
        
//         // Queue for BFS traversal, each
//         // element is a pair containing node
//         // and its vertical and level information
//         queue<pair<Node*, pair<int, int>>> todo;
        
//         // Push the root node with initial vertical
//         // and level values (0, 0)
//         todo.push({root, {0, 0}});
        
//         // BFS traversal
//         while(!todo.empty()){
//             // Retrieve the node and its vertical
//             // and level information from
//             // the front of the queue
//             auto p = todo.front();
//             todo.pop();
//             Node* temp = p.first;
            
//             // Extract the vertical and level information
//             // x -> vertical
//             int x = p.second.first;  
//             // y -> level
//             int y = p.second.second; 
            
//             // Insert the node value into the
//             // corresponding vertical and level
//             // in the map
//             nodes[x][y].insert(temp->data);
            
//             // Process left child
//             if(temp->left){
//                 todo.push({
//                     temp->left,
//                     {
//                         // Move left in
//                         // terms of vertical
//                         x-1, 
//                         // Move down in
//                         // terms of level
//                         y+1  
//                     }
//                 });
//             }
            
//             // Process right child
//             if(temp->right){
//                 todo.push({
//                     temp->right, 
//                     {
//                         // Move right in
//                         // terms of vertical
//                         x+1, 
//                         // Move down in
//                         // terms of level
//                         y+1  
//                     }
//                 });
//             }
//         }
        
//         // Prepare the final result vector
//         // by combining values from the map
//         vector<vector<int>> ans;
//         for(auto p: nodes){
//             vector<int> col;
//             for(auto q: p.second){
//                 // Insert node values
//                 // into the column vector
//                 col.insert(col.end(), q.second.begin(), q.second.end());
//             }
//             // Add the column vector
//             // to the final result
//             ans.push_back(col);
//         }
//         return ans;
//     }
// };

// Helper function to
// print the result
// void printResult(const vector<vector<int>>& result) {
//     for(auto level: result){
//         for(auto node: level){
//             cout << node << " ";
//         }
//         cout << endl;
//     }
//     cout << endl;
// }

// int main() {
//     // Creating a sample binary tree
//     Node* root = new Node(1);
//     root->left = new Node(2);
//     root->left->left = new Node(4);
//     root->left->right = new Node(10);
//     root->left->left->right = new Node(5);
//     root->left->left->right->right = new Node(6);
//     root->right = new Node(3);
//     root->right->right = new Node(10);
//     root->right->left = new Node(9);

//     Solution solution;

//     // Get the Vertical traversal
//     vector<vector<int>> verticalTraversal =
//                     solution.findVertical(root);

//     // Print the result
//     cout << "Vertical Traversal: ";
//     printResult(verticalTraversal);

//     return 0;
// }
                            
                        
15000