Top view of binary tree in C++

In this tutorial, we will learn about the top view of the binary tree in c++. We will also see the code implementation to find out the top view of the binary tree.

We will also see the example to understand the concept in a better way.

Top view of binary tree

The Top view of the binary tree is defined by the sets of nodes of a tree visible when the tree is viewed from the top.

Some related posts:

Let’s see the example,

                     1
                   /   \
                 2      3
               /   \  /   \
             4     5  6     7
Top view of the above binary tree is 1 2 3 4 7

                            1
                          /   \
                         2     6
                          \   /   \
                           3 7     9          top view is 1-2-6-9.
                         /  \  \    
                        4    5  8     

Hence, in above example we can see the top view of the given binary tree.

Now, let’s see the pseudocode,

1.Create a structure 
        struct horizontal{
               Node* node;
                   int hd;
        };
2.Create a empty queue<horizontal>q and initially push the root node with hd=0;
3.while q is not empty do
       .Pop the top node from the queue.
       .check the value of hd of this node exist or not in queue.
           if not present means it is top view node hence print it.
       .Push the left node with hd=hd-1;
       .Push the right node with hd=hd+1;

Now, let’s see the code.

Code implementation in c++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
};
Node* create(int x){
  Node* temp=(Node*)malloc(sizeof(Node));
  temp->data=x;
  temp->left=NULL;
  temp->right=NULL;
  return temp;
}
struct horizontal{
        Node* node;
        int hd;
    };
void topView(struct Node *root)
{
    horizontal temp;
    queue<horizontal>hr;
    map<int,int>m;
    map<int,int>::iterator it;
    temp.node=root;
    temp.hd=0;
    hr.push(temp);
    while(!hr.empty()){
        horizontal temp=hr.front();hr.pop();
        it=m.find(temp.hd);
        if(it==m.end()){
            cout<<temp.node->data<<" ";
            m.insert(pair<int,int>(temp.hd,(temp.node)->data));
        }
        if(temp.node->left!=NULL){
            horizontal n;
            n.node=(temp.node)->left;
            n.hd=(temp.hd)-1;
            hr.push(n);
        }
        if(temp.node->right!=NULL){
            horizontal n;
            n.node=(temp.node)->right;
            n.hd=(temp.hd)+1;
            hr.push(n);
        }
    }
}
int main(){
  Node* root=create(1);
  root->left=create(2);
  root->left->right=create(3);
  root->left->right->left=create(4);
  root->left->right->right=create(5);
  root->right=create(6);
  root->right->left=create(7);
  root->right->left->right=create(8);
  root->right->right=create(9);
  cout<<"Top view of the binary tree is: ";
  topView(root);
}

OUTPUT

Top view of the binary tree is: 1 2 6 9

You may also learn,

Boundary traversal of the Binary tree in C++

Find out the Diameter of the Binary Tree in C++

Leave a Reply

Your email address will not be published. Required fields are marked *