Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The maximum distance-based approach
2.1.
Algorithm for the maximum distance-based approach
2.2.
Implementation of the maximum distance-based approach
3.
Frequently Asked Questions
3.1.
What is horizontal distance in a binary tree?
3.2.
What is the top view of a binary tree?
3.3.
How do you find the top view of a binary tree?
3.4.
What is the top of a binary tree called?
3.5.
What is the diameter of a binary tree?
4.
Conclusion
Last Updated: Mar 27, 2024

Top View of A Binary Tree | Part-2

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

We have already seen the basic and two-variable methods to solve this problem in the previous blog on printing the top view of a binary tree.
Before diving into the next method, let's again take a look at the problem briefly-
Suppose we have to print the top view of a binary tree given below. 

Tree

We will get the following output-

8 4 2 1 3 7

So, we can say that the top view of a binary tree refers to the set of nodes visible to an observer if we view the tree from an axis above the root and parallel to the levels of the tree. Or if a set of nodes is formed by selecting the topmost nodes of all the vertical orders of the binary tree. 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 also discussed the basic method and a depth-based method in the previous blog. But in this blog, we will be focusing on the method using the max distance on both branches of the binary tree. So, let’s begin with the blog-.

(Also see, Data Structures)

The maximum distance-based approach

This is another method based on the level order traversal of the binary tree. We keep track of the minimum left horizontal distance from the root(as the value of the distance is negative on the left side) and the maximum horizontal distance on the right of the node. 

Whenever a node comes with a distance lesser than the minimum distance on the left or greater than the maximum distance on the right, it will be the topmost node in its vertical distance. Thus, it gets included in the top view of a binary tree and in order to maintain the left-to-right ordering of nodes while printing the top view of the binary tree we maintain a stack and vector while performing level order traversal.

Algorithm for the maximum distance-based 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. Push the root and its horizontal distance into the queue.
  4. Create variables to maintain the minimum distance value in the left and maximum distance in the right from the root.
  5. Declare a stack to store the new nodes with the highest values in the left and a vector to hold nodes in the right branch.
  6. Start the level order traversal of the binary tree by running a loop while the queue is not empty-
  7. If we find a node with a horizontal distance lesser than the minimum distance on the left(negative value), we push it into the stack.
  8. If we find a node with a horizontal distance more than the maximum distance in the right (positive value), we push it into the vector.
  9. Now print the values in both stack and vector to get the result. 

Implementation of the maximum distance-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 printtopview(node* root)
{
    //Queue of pairs of the node and their horizontal 
    //distances.
    queue<pair<node*, int> > que;
    //Push root and its horizontal distance as 0 into the //queue.
    que.push(make_pair(root, 0));
    int hordist=0, lft=0, rgt=0;
    //Stack to store nodes in top view on the left side 
    //of the root.
    stack<int> nodesonleft;
    //Vector to store nodes in top view on the right side 
    // of the root.
    vector<int> nodesonright;
    node* curr;
    //while loop until the queue is not empty.
    while(que.size())
    {
        //Taking out front node in the queue and its 
        //distance from the node.
        curr=que.front().first;
        hordist=que.front().second;
        //If a node has horizontal distance lesser than 
        //left most node,Or if it has horizontal distance 
        //greater than the rightmost node.
        if(hordist<lft)
        {
            nodesonleft.push(curr->data);
            lft=hordist;
        }
        else if(hordist>rgt)
        {
            nodesonright.push_back(curr->data);
            rgt=hordist;
        }
        //Pushing the left and right children of current 
        //node into the queue.
        if(curr->left)
        {
            que.push(make_pair(curr->left, hordist-1));
        }
        if(curr->right)
        {
            que.push(make_pair(curr->right, hordist+1));
        }
        que.pop();
    }
    //Printing nodes on the left.
    while(nodesonleft.size()) 
    {
        cout<<nodesonleft.top()<<" ";
        nodesonleft.pop();
    }
    //Printing the root.
    cout<<root->data<<" ";
    //Printing nodes on the right. 
    for(auto x:nodesonright) 
    {
        cout<<x<<" ";
    }
}
//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 the above approach is O(N), where N is the number of nodes in the binary tree.

The space complexity of the above approach is O(N).

Check out this problem - Mirror A Binary Tree

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

Frequently Asked Questions

What is horizontal distance in a binary tree?

The perpendicular distance of a node from an axis passing through the node of a tree is called its horizontal distance.

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.

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.

What is the diameter of a binary tree?

The number of nodes on the longest paths between two end nodes is known as the diameter of the binary tree.

Conclusion

In this blog, we have discussed an additional method we can use to print the top view of a binary tree, other than the ones discussed in the previous blog-

This is a method based on the level order traversal of the binary tree. In it, we use two-variable of to keep track of the leftmost and rightmost horizontal distance traversed so far during the level order traversal of the binary tree. Now any node that has a value more than the maximum distance in the right, Or less than the minimum distance on the left(distance towards the left is negative), is a node that will be visible in the top view of a binary tree.

You must check out part 1 of this blog to know more methods and develop a wholesome understanding of the top view of a binary tree. You can practice similar problems on Coding Ninjas Studio as well.

Recommended Reading:

 

Recommended problems -

 

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, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass