Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.7 kB
0
Indexable
Never


// } Driver Code Ends
/*
struct Node
{
    int data;
    Node* left;
    Node* right;
};
*/
class Solution
{
    public:
    //Function to return a list of nodes visible from the top view 
    //from left to right in Binary Tree.
    vector<int> topView(Node *root)
    {
        vector<int> topView;
        
        if (root == NULL) return topView;
        
        // 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();
                
                // update the horzDistMap only if an element appear at new horzDist which isn’t present in map yet.
                // Don't update if earlier an element appeared at a previous level this particular horzDist.
                if (horzDistMap[horzDist] == 0)
                    horzDistMap[horzDist] = curr -> data;
                    
                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)
            topView.push_back(entry.second);
    }

};