Description

Submission

• Level Order Traversal
• vector<pair<Node*, int>> has no iterator, so we can only use index representation

#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;
           }
        }

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

*/


    void topView(Node * root) {
        map<int, int> m;              // (hd, value)
        vector<pair<Node*, int>> s; // (node, hd)
        s.push_back(make_pair(root, 0));
        int max_hd = 0, min_hd = 0;
        for(int i = 0; i < s.size(); ++i) {
            auto iter = s[i];
            if(m.find(iter.second) == m.end()) {
                m.insert(make_pair(iter.second, iter.first->data));
                if(iter.second > max_hd) max_hd = iter.second;
                if(iter.second < min_hd) min_hd = iter.second;
            }

            if(iter.first->left) s.push_back(make_pair(iter.first->left, iter.second - 1));
            if(iter.first->right) s.push_back(make_pair(iter.first->right, iter.second + 1));
        }

        for(int i = min_hd; i <= max_hd; ++i) {
            cout << m[i] << " ";
        }
    }


}; //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;
}