Top view of a binary tree | Part-1

Gorakhnath yadav
Last Updated: May 13, 2022

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-

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 simplest words, the top view of a binary tree refers to the set of the 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.

The 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 basic approach-

  1. Create a binary tree or take it from user input.
  2. Create a queue to hold nodes during the level order traversal of the tree.
  3. Create a map to keep track of the visited nodes.
  4. Start the level order traversal of the binary tree by pushing the root and its horizontal distance into the queue.
  5. Now run a loop while the queue is not empty-
  6. Check if the map has a node at that horizontal distance; if no, push it in the map.
  7. Push the left and right child of the node in the queue, and update the value of their horizontal distance.
  8. Pop the element from the queue.
  9. Repeat step 5 with the front of the queue.
  10. Then print the values in 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

 

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).

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-

  1. Create a binary tree or take it from user input.
  2. Create a map that stores the horizontal distance of the nodes and a pair of nodes and their level as key-value pairs.
  3. Then we use a function to push the node into the map along its horizontal distance and level.
  4. 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.
  5.  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.
  6. 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).

Frequently Asked Questions-

  1. 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.
     
  2. 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.
     
  3. What is the top of a binary tree called?

    The top of a binary tree is called the root node.
     
  4. 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.
     
  5. What is the width of a binary tree?

The width of the binary tree is the level with the most number of nodes in it.

Key takeaways-

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 its 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 CodeStudio as well.

 

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think