Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Basic Approach
2.1.
Algorithm for a basic approach
2.2.
Implementation of the basic approach
3.
The level-based approach
3.1.
Algorithm for the level-based approach
3.2.
Implementation of the level-based approach
4.
Frequently Asked Questions
4.1.
What is the top view of a binary tree?
4.2.
How do you find the top view of a binary tree?
4.3.
What is the top of a binary tree called?
4.4.
What is a treetop view?
4.5.
What is the width of a binary tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Top view of a binary tree

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM
Top view of binary tree

Introduction

Let's begin with understanding the task first. Suppose there is a programming problem that asks you to print the top view of a binary tree. For example, consider the following binary tree-

top view of a binary tree

Now, if you print the top view of a binary tree, you will get the following output-

8 4 2 1 3 7 

 

So, we can say that, in the simplest words, the top view of a binary tree refers to the set of nodes visible if we view the tree from an axis parallel to the levels of the tree. Or if we take the topmost nodes of all the vertical orders in it. Vertical orders refer to the set of nodes at a particular horizontal distance.

 

Though there are various methods to print the top view of a binary tree, we will start with discussing the basic method, which does the level order traversal of the binary tree and prints all the topmost nodes for each value of the horizontal distance. Then move on to advanced methods like two-variable methods etc.

Recommended: Try the Problem yourself first before moving on to the solution.

Basic Approach

This method does find vertical orders in the tree with the help of the horizontal distance of each node, the horizontal distance of the left child of a node is one less than the parent, and the right child is one more than the parent. 

Now we do the level order traversal of the tree to ensure that nodes appear in the top to bottom order for every vertical order, and we maintain a hashmap to keep track of the visited nodes for each vertical order.

Algorithm for a basic approach

  • Create a binary tree or take it from user input.
  • Create a queue to hold nodes during the level order traversal of the tree.
  • Create a map to keep track of the visited nodes.
  • Start the level order traversal of the binary tree by pushing the root and its horizontal distance into the queue.
  • Now run a loop while the queue is not empty-
  • Check if the map has a node at that horizontal distance; if not, push it into the map.
  • Push the left and right child of the node in the queue, and update the value of their horizontal distance.
  • Pop the element from the queue.
  • Repeat step 5 at the front of the queue.
  • Then print the values on the map.

Implementation of the basic approach

#include <bits/stdc++.h>
using namespace std;
struct node 
{
    int data;

    int hordist;
    struct node *left, *right;
};
//To create a new node for the binary tree.
node *createnode(int data)
{
    node *var = new node;
    var->data = data;
    var->left = var->right = NULL;
    return var;
}
//Function, which takes the root node of the binary tree 
//as argument and prints its top view.
void printtopview(node* root)
{
    //base case.
    if(root==NULL)
    {
        return;
    }
    //Queue to store nodes during level order traversal 
    //of the tree.
    queue<node*> que;
    //Map to take horizontal distance and node as key 
    //value pairs.
    map<int, int> mp;
    int hordist=0;
    root->hordist=hordist;
    //Level order traversal of the binary tree.
    que.push(root);
    while(que.size())
    {
        hordist=root->hordist;
        //If the map has no visited node for that 
        //horizontal distance, push the node in the map.
        if(mp.count(hordist)==0)
        {
            mp[hordist]=root->data;
        }
        //Continue the traversal by pushing the left anf 
        //right nodes into the queue, with the updated 
        //value of their horixzontal distance.
        if(root->left)
        {
            root->left->hordist=hordist-1;
            que.push(root->left);
        }
        if(root->right)
        {
            root->right->hordist=hordist+1;
            que.push(root->right);
        }
        que.pop();
        root=que.front();
    }
    //To print the top view of a binary tree.
    for(auto itr=mp.begin();itr!=mp.end();itr++)
    {
        cout<<itr->second<<" ";
    }
}
//Driver function.
int main()
{
    //Creating the binary tree.
    node *root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->left=createnode(4);
    root->left->right=createnode(5);
    root->right->left=createnode(6);
    root->right->right=createnode(7);
    root->left->left->left=createnode(8);
    root->left->left->right=createnode(9);
    //Function Call.
    printtopview(root);
    return 0;
}

 

Output-

8 4 2 1 3 7

 

Time Complexity: The time complexity of this approach is O(N*logN), an insertion in a map takes O(logN) time, and we had N nodes to process.

Space Complexity: The space complexity of this approach is O(N).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

The level-based approach

In this approach, we also keep track of the level of the nodes along with their horizontal distance from the root. If we find a node with the same horizontal distance, then we check for its level. If the new node has a lower level, we replace it.

Algorithm for the level-based approach

  • Create a binary tree or take it from user input.
  • Create a map that stores the horizontal distance of the nodes and a pair of nodes and their level as key-value pairs.
  • Then we use a function to push the node into the map along its horizontal distance and level.
  • Now the Function in step three does check if the map contains any value for the horizontal distance of the current node; if yes, compares both nodes and keeps the one with a lower level., or in case this is the first node corresponding to this horizontal distance it gets pushed into the map.
  •  We recursively call the Function in step 3 for the left and right child of the current node with updated horizontal distance and level values.
  • Then we print the values stored in the map.

Implementation of the level-based approach

#include <bits/stdc++.h>
using namespace std;
struct node 
{
    int data;

    int hordist;
    struct node *left, *right;
};
//To create a new node for the binary tree.
node *createnode(int data)
{
    node *var = new node;
    var->data = data;
    var->left = var->right = NULL;
    return var;
}
void completethemap(node* root, int hordist, int level, map<int , pair<int, int> >&mp)
{
    //Base case.
    if(root==NULL)
    {
        return;
    }
    //If node is first one for its horizontal distance, 
    //push it into the map. Or if a node is present, 
    //check the level, keep the one with lower level.
    if(mp.count(hordist)==0)
    {
        mp[hordist]=make_pair(root->data, level);
    }
    else if(mp[hordist].second>level)
    {
        mp[hordist]=make_pair(root->data, level);
    }
    //Recursively call this function for left and right childs as well.
    completethemap(root->left,hordist-1,level+1,mp);
    completethemap(root->right,hordist+1,level+1,mp);
}
//Function, which takes the root node of the binary tree 
//as argument and prints its top view.
void printtopview(node* root)
{
    //Map of horizontal distance and a pair of node and 
    //its level as key value pairs.
    map<int, pair<int, int> > mp;
    completethemap(root, 0, 0, mp);   
    //To print the top view of the binary tree.
    for(auto itr=mp.begin();itr!=mp.end();itr++)
    {
        cout<<itr->second.first<<" ";
    }
}
//Driver function.
int main()
{
    //Creating the binary tree.
    node *root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->left=createnode(4);
    root->left->right=createnode(5);
    root->right->left=createnode(6);
    root->right->right=createnode(7);
    root->left->left->left=createnode(8);
    root->left->left->right=createnode(9);
    //Function Call.
    printtopview(root);
    return 0;
}

 

 

Output-

8 4 2 1 3 7

The time complexity of this approach is O(N*logN), an insertion in a map takes O(logN) time, and we had N nodes to process.

The time complexity of this approach is O(N).

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

What is the top view of a binary tree?

The top view of a binary tree is the set of nodes that will be visible if we look at the binary tree from the top. So, the root node will always be there in the top view. Other nodes will be considered on the basis of the topmost nodes at a particular horizontal distance. So, the root node will always be there in the top view. Other nodes will be considered on the basis of the topmost nodes at a particular horizontal distance.

How do you find the top view of a binary tree?

We can find the top view using the methods described in the blog, which mainly involves the level order traversal of the binary tree, and then we pick the nodes on the top of their vertical order.

What is the top of a binary tree called?

The top of a binary tree is called the root node. This node will always be visible when we look at the tree from the top, that’s why it is called the top of the binary tree.

What is a treetop view?

A treetop view refers to the set of the tree elements visible to use if we look at a tree from an axis parallel to the levels in it and above the tree's root node.

What is the width of a binary tree?

The width of one level is defined as the distance between the end nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end nodes that would be present in a full binary tree extending down to that level are also counted.

Conclusion

In this blog, we have discussed the methods we can use to print the top view of a binary tree-

  • The first method is based on the level order traversal of the binary tree. We also use a hashmap to keep track of the visited node for each vertical order in the tree during the level order traversal. And any nodes that appear for the first time for their horizontal distance during the level order traversal will be included in the top view of a binary tree.
  • The second method is the level-based approach. In it, we find the level of the node along with its horizontal distance, and for every vertical order, pick the node with the lowest level. This method uses a map with horizontal distance and a pair of nodes and their level as key-value pairs.

You must check out the next part of this blog to know about more advanced methods on the top view of a binary tree. You can practice similar problems on Coding Ninjas Studio as well.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Print Right View of A Binary Tree
Next article
Top View of A Binary Tree | Part-2
Live masterclass