Print Top View of Binary Tree

Introduction 

In this article, we will learn about how to get the top view of Binary tree using multiple approaches. 

The collection of nodes visible from the top of a binary tree is known as the top view. Print the top view of a binary tree given. Printing the output nodes in any order is possible.

If x is the topmost node at its horizontal distance, it appears in the output. The horizontal distance of a node’s left child is equal to x minus 1, and the horizontal distance of a node’s right child is equal to x plus 1.

Method 1: Using Deque

If we can give the root a vertical height index =0 then create a count of the left and rightindexes upto ehich we have seen the nodes then each time:

• if vertical height is lesser then left index then it is a new node at vertical height index l-1.
• if vertical height is greater then right index then it is a new node at vertical height index r+1.

Role of deque :

as we need to keep track of the top view feom the leftmost to the rightmost node so,

1. if we find a new node at left to be in the top view we insert that node to the front of the queue.
2. if we find a new node to the right of previous rightmost node then we add this node to rear/back of the queue.

Hence at last the deque will contain all the top view nodes in order from leftmost to rightmost.

// C++ program for top// view of binary tree #include <bits/stdc++.h>using namespace std; // Structure of the binary treestruct Node{ Node* left; Node* right; int hd; int data;}; // function to create a new nodeNode* newNode(int key){ Node* node = new Node(); node -> left = node -> right = NULL; node -> data = key; return node;} //Function to return a list of nodes visible from the top view //from left to right in Binary Tree.vector<int> topview(Node* root){ deque<int> v;        vector<int> a;        if(!root) return a;        queue<pair<Node*,int>> q;         q.push({root,0});     // root node is always in the top-view so:         v.push_back(root->data);     // intially leftmost and rightmost inndexes = root index = 0        int l=0;              int r=0;        while(q.size()){            Node *t = q.front().first;            int vh = q.front().second;            q.pop();             // new node has a vertical level greater than rightmost tree level till now so, add it to top-view            if(vh>r) {                r=vh;                v.push_back(t->data);            }           // new node has a vertical level lesse than leftmost tree level till now so, add it to top-view            if(vh<l) {                l=vh;                v.push_front(t->data);            } //insert children            if(t->left) q.push({t->left,vh-1});               if(t->right) q.push({t->right,vh+1});         }        while(v.size()){            a.push_back(v.front());            v.pop_front();        }                return a; } // Driver Program to test above functionsint main(){ /* Create following Binary Tree   3 / \ 4 5 \ 6   \   7     \                   8 */ Node* root = newNode(3); root -> left = newNode(4); root -> right = newNode(5); root -> left -> right = newNode(6); root -> left -> right -> right = newNode(7); root -> left -> right -> right -> right = newNode(8); cout << “Following are nodes in top view of Binary ” “Tree\n”; vector<int> ans= topview(root); for(auto i: ans) cout<<i<<” “; return 0;}

Output:

Following are nodes in top view of Binary Tree4 3 5 8

Method 2: Using Map

here, we store the vertical hight index of the node and check if the index already exists in the map that means we have seen a node above this node in the tree so we dont need this node in the Top view.

else if the vh of the node is not in the map means this vertical level did not had any node so this node is the first node in this vetical level or coloumn so add it to map.

all the nodes in the map are the nodes which are encountered first in the vertical traversal.

// C++ program for top// view of binary tree #include <bits/stdc++.h>using namespace std; // Structure of the binary treestruct Node{ Node* left; Node* right; int hd; int data;}; // function to create a new nodeNode* newNode(int key){ Node* node = new Node(); node -> left = node -> right = NULL; node -> data = key; return node;} //Function to return a list of nodes visible from the top view //from left to right in Binary Tree.vector<int> topview(Node* root){ map<int,int> v;         vector<int> a;        if(!root) return a;        queue<pair<Node*,int>> q;        q.push({root,0});         while(q.size()){            Node *t = q.front().first;            int vh = q.front().second;            q.pop();             // if this column index already has a      //node we dont need to change it             if(v[vh]==0) v[vh]=t->data;                if(t->left) q.push({t->left,vh-1});            if(t->right) q.push({t->right,vh+1});         }       // all the nodes in the map are the nodes which are    // encountered first in the verical traversal so  gives us the top view of the tree                for(auto x:v) a.push_back(x.second);            return a; } // Driver Program to test above functionsint main(){ /* Create following Binary Tree   3 / \ 4 5 \ 6   \   7     \                   8 */ Node* root = newNode(3); root -> left = newNode(4); root -> right = newNode(5); root -> left -> right = newNode(6); root -> left -> right -> right = newNode(7); root -> left -> right -> right -> right = newNode(8); cout << “Following are nodes in top view of Binary ” “Tree\n”; vector<int> ans= topview(root); for(auto i: ans) cout<<i<<” “; return 0;}

Output:

Following are nodes in top view of Binary Tree4 3 5 8