Top View of Binary Tree

by · January 22, 2021

“Top View of Binary Tree” is one of the foremost algorithmic problem asked in technical interviews of product-based companies. Here, we are given a binary tree and our task is to write a program to print the top view of given binary tree.

Top View of Binary Tree is referred to those nodes of binary tree which can be seen from top of the tree.

Top View of Binary Tree
Top View of Binary Tree

The idea here is similar to vertical order traversal of binary tree. We will perform the vertical order traversal and print only those nodes which are first nodes of vertical order line.

The steps required to print top view of Binary Tree are as follows:

  1. Create a map which store the vertical order line number and corresponding first/top node value.
  2. Create a queue which can accommodate both node and corresponding horizontal distance with root node.
  3. Insert the root node into queue and 0 as horizontal distance.
  4. Perform following steps until queue is node empty.
    • Pop front Element of queue.
    • Check if popped horizontal distance already present in the map or not. If not, insert the popped node value into map.
    • If left child exists of popped node, insert into queue with horizontal distance as current HD-1.
    • If right child exists of popped node, insert into queue with horizontal distance as current HD+1.
  5. Print the map data which contains top view.

C++ Program to print top view of binary tree is as follows:

/* C++ Program to print top view of Binary Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to print top view of Binary Tree */
void topView(Node *root)
{
    /* Base Case */
    if(root == NULL)
    return;
    
    /*
        Create a map which store top view nodes
        key: vertical order line
        pair: Top node of vertical order line
    */
    map<int, int> mp;
    
    /*
        Create queue which store both node and corresponding HD
    */
    queue<pair<Node*, int>> que;
    int hd = 0;
    
    que.push(make_pair(root,hd));
    
    while(!que.empty())
    {
        /* Pop front Node */
        pair<Node *,int> temp = que.front();
        que.pop();
        Node *temp_node = temp.first;
        int currHD = temp.second;
        
        /* 
            If vertical order line is not present in map, 
            then insert the node value in the map, as it will the 
            first node of the verical order line
        */
        if(mp.find(currHD) == mp.end())
        {
            mp[currHD] = temp_node -> data;
        }
        
        if(temp_node -> left)
        que.push(make_pair(temp_node -> left, currHD - 1));
        
        if(temp_node -> right)
        que.push(make_pair(temp_node -> right, currHD + 1));
    }
    
    /* Print map, which contain top view nodes */
    map<int, int> :: iterator itr;
    for(itr = mp.begin(); itr != mp.end(); ++itr)
    {
        cout << itr -> second << " ";
    }
}

int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to print top view of binary tree*/
    cout<<"The top View of Given Binary Tree is:\n";
    topView(root);
}

OUTPUT:

The top View of Given Binary Tree is:
4 2 1 3 7

Related Posts:

  1. Bottom View of Binary Tree
  2. Delete Complete Binary Tree
  3. Check if two trees are mirror Trees of Each Other
  4. Convert Binary Tree to its Mirror Tree
  5. Check if Binary Tree is Symmetric or Not
  6. Print All Root to Leaf Paths in a Binary Tree
  7. Introduction to Tree Data Structure
  8. Binary Tree Traversals
  9. Print All Leaf Nodes of a Binary Tree
  10. Count Number of Nodes in a Binary Tree
  11. Print Alternate Levels of Binary Tree
  12. Maximum Width of Binary Tree
  13. Level Order Tree Traversal
  14. Left View of Binary Tree
  15. Right View of Binary Tree
  16. Compute Height of Binary Tree
  17. Inorder Tree Traversal Using Stack
  18. Preorder Tree Trasversal Using Stack
  19. Postorder Tree Traversal Using Stack
  20. Vertical Order Tree Traversal

You may also like...