Diagonal Traversal

vector<int> diagonalPath(BinaryTreeNode<int>* root) {
    // Write your code here.
    vector<int>result;
    if(root==NULL)
        return result;

    queue<pair<BinaryTreeNode<int>*,pair<int,int>>>q;
    q.push({root, {0, 0}});

    map<int,vector<int>>mp;

    while(!q.empty())
    {
        int size=q.size();

        for(int i=0;i<size;i++)
        {
            BinaryTreeNode<int>* node=q.front().first;
            int level=q.front().second.first;
            int vert=q.front().second.second;

            q.pop();

            if(node->left)
                q.push({node->left,{level+1,vert-1}});

            if(node->right)
                q.push({node->right,{level+1,vert+1}});

                mp[abs(vert-level)].push_back(node->data);

        }
    }

    for (const auto& it : mp) {
        result.insert(result.end(), it.second.begin(), it.second.end());
    }

    return result;
}