Untitled

class Solution {
  public:
    vector <int> bottomView(Node *root) {
        vector<int> bottomView;
        
        if (root == NULL) return bottomView;
        
         // This stores horizontal distance of nodes from centre line like -1, -2, 0, 2 etc.
         // HorzDist of root is 0 and -1, 1 for its left and right child respectively.
        map<int, int> horzDistMap;
        
        // Stores node and its horzDist
        queue<pair<Node *, int>> q;
        q.push({root, 0});
        
        while (!q.empty()) {
            int levelSize = q.size();
            
            for (int i = 1; i <= levelSize; i++) {
                Node *curr = q.front().first;
                int horzDist = q.front().second;
                q.pop();
                
                horzDistMap[horzDist] = curr -> data; // at each level update the node at a horzDist.
                    
                if (curr -> left != NULL)
                    q.push({curr -> left, horzDist - 1});
                    
                if (curr -> right != NULL)
                    q.push({curr -> right, horzDist + 1});
            }
        }
        
        // print nodes from -ve horzDist to +ve.
        for (auto entry : horzDistMap)
            bottomView.push_back(entry.second);
            
        return bottomView;
    }
};