codeDump/cpp/BottomViewOfBinaryTree.cpp at main · akkupy/codeDump · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// https://practice.geeksforgeeks.org/problems/bottom-view-of-binary-tree/1


class Solution {
  public:
    vector <int> bottomView(Node *root) {
        // Your Code Here
                vector<int> ans;
        map<int,int> hdMapping;
        queue<pair<Node*,int>> q;
        q.push(make_pair(root, 0));

        while(!q.empty()){

            pair<Node*,int> front= q.front();
            q.pop();
            Node* currNode= front.first;
            int hd= front.second;

            hdMapping[hd]= currNode->data;

            if(currNode->left)
                q.push(make_pair(currNode->left, hd-1));
            if(currNode->right)
                q.push(make_pair(currNode->right, hd+1));

        }

        for( auto i : hdMapping)
            ans.push_back(i.second);

        return ans;
    }
};