Top view of a Binary tree, C++ (gcc)

Top view of a Binary tree

#include<bits/stdc++.h>

using namespace std;

class Node {
    public:
        int data;
        Node *left;
        Node *right;
        Node(int d) {
            data = d;
            left = NULL;
            right = NULL;
        }
};

class Solution {
    public:
  		Node* insert(Node* root, int data) {
            if(root == NULL) {
                return new Node(data);
            } else {
                Node* cur;
                if(data <= root->data) {
                    cur = insert(root->left, data);
                    root->left = cur;
                } else {
                    cur = insert(root->right, data);
                    root->right = cur;
               }

return root;
           }
        }

vector<int> getLevelOrder(Node * root){
        vector<int> v;
        queue<Node *> q;
        if(root==NULL)
            return v;
        else{
            q.push(root);
            while(!q.empty()){
                v.push_back(q.front()->data);
                if(q.front()->left)
                    q.push(q.front()->left);
                if(q.front()->right)
                    q.push(q.front()->right);
                q.pop();
            }
        }
        return v;
    }
    void getVerticalView(map<int,pair<int,int> >& mp, Node* root, int d, const vector<int> levelOrder){
        if(root==NULL)
            return;
        int idx = distance(levelOrder.begin(),find(levelOrder.begin(),levelOrder.end(),root->data));
        if(mp[d].first==0 || idx < mp[d].second){
            mp[d].first = root->data;
            mp[d].second = idx;
        }
        if(root->left)
            getVerticalView(mp,root->left,d-1,levelOrder);
        if(root->right)
            getVerticalView(mp,root->right,d+1,levelOrder);
    }
    void topView(Node * root) {
        vector<int> levelOrder = getLevelOrder(root);
        map<int,pair<int,int> > mp;  // Hd distance : value,index in level order
        getVerticalView(mp,root,0, levelOrder);
        for(auto i: mp){
            cout<<i.second.first<<" ";
        }
    }

}; //End of Solution

int main() {
  
    Solution myTree;
    Node* root = NULL;
    
    int t;
    int data;

std::cin >> t;

while(t-- > 0) {
        std::cin >> data;
        root = myTree.insert(root, data);
    }
  
	myTree.topView(root);
    return 0;
}


run \| edit \| history \| help	0