Top View of A Binary Tree | Part-2

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. 

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;
}

You can also try this code with Online C++ Compiler

Run Code

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