#include <bits/stdc++.h>
using namespace std;

// Structure representing each node of the binary tree
struct Node {
    // Value stored in the node
    int data;
    // Pointer to the left child
    Node* left;
    // Pointer to the right child
    Node* right;
    // Constructor to initialize a node with a value
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Class containing the logic for top view
class Solution {
public:
    // Function to return the top view of the binary tree
    vector<int> topView(Node* root) {
    vector<int> ans;
    if(root==NULL)
    {
        return;
    }
    map<int,int> mp;
    queue<pair<Node*,int> q;
    q.push({root,0});
    while(!q.empty())
    {
        auto it=q.front();
        q.pop();
        Node* node=it.first;
        int line=it.second;
        if(mp.find(line)==m.end())
        {
            mp[line]=node->data;
        }
        if(node->left!=NULL)
        {
            q.push({node->left,line-1});
        }
        if(node->right!=NULL)
        {
            q.push({node->right,line+1});
        }
    }
    for(auto it:mp)
    {
        ans.push_back(it.second);
    }
    return ans;
    }
};

// Driver code
int main() {
    // Create the sample binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->left->left = new Node(4);
    root->left->right = new Node(10);
    root->left->left->right = new Node(5);
    root->left->left->right->right = new Node(6);
    root->right = new Node(3);
    root->right->right = new Node(10);
    root->right->left = new Node(9);

    // Create a Solution object
    Solution solution;

    // Get the top view
    vector<int> result = solution.topView(root);

    // Print the top view traversal
    cout << "Top View Traversal: ";
    for (auto node : result) {
        cout << node << " ";
    }
    return 0;
}