top view cpp

// program to print the top view of binary tree
#include <iostream>
#include <queue>
#include <map>

using namespace std;

// node class
class node{
public:
    int data;
    int hd;
    node* left;
    node* right;
};

// function that returns a pointer to new node
node* createNode(int element){
    node* temp = (node*) malloc(sizeof(node));
    temp->data = element;
    temp->hd = -1;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

// function to print Top View of Tree
void top_view(node *root){
    if(root == NULL){
        return;
    }

    // we keep track of the horizontal distance of the node from the root node
    // to print the bottom view
    int hd = 0; // hd = horizontal distance from the root node
    hd = root->hd;

    // creating a Queue for storing node for level wise traversal
    // and a map for mapping horizontal distances with the node data
    queue<node *> Q;
    map<int, int> Map;

    Q.push(root);
    while(!Q.empty()){

        // pop the first node from the queue
        node *p = Q.front();
        Q.pop();

        hd = p->hd;

        // if a horizontal distance is already mapped with a value then
        // we don't replace it with a new value
        if(Map.find(hd) == Map.end()) {
            Map[hd] = p->data;
        }

        // increase the horizontal distance from the root node in negative direction
        // and push the node on queue
        if(p->left != NULL){
            p->left->hd = hd - 1;
            Q.push(p->left);
        }

        // increase the horizontal distance from the root node in positive direction
        // and push the node on queue
        if(p->right != NULL){
            p->right->hd = hd + 1;
            Q.push(p->right);
        }
    }

    // print the generated map
    cout<<"\n\nTop view of the binary tree is : "<<endl;
    for (auto iter = Map.begin(); iter != Map.end(); iter++){
        cout<<iter->second <<" ";
    }
}


int main() {
    node* head = createNode(1);
    head->left = createNode(2);
    head->right = createNode(3);
    head->left->left = createNode(4);
    head->left->right = createNode(5);
    head->right->right = createNode(6);
    head->left->left->right = createNode(7);
    head->right->right->left = createNode(8);
    head->left->left->right->left = createNode(9);
    head->left->left->right->left->left = createNode(10);
    head->right->right->left->right = createNode(11);
    head->hd = 0;
    top_view(head);
    return 0;
}

/*

Top view of the binary tree is :
10 4 2 1 3 6
Process finished with exit code 0

*/