Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Top View

Moderate
0/80
Average time to solve is 42m
profile
Contributed by
13 upvotes
Asked in companies
SamsungAdobeMakeMyTrip

Problem statement

Given a binary tree. Print the Top View of Binary Tree. Print the nodes from left to right order.

Example:
Input:

Alt text

Output: 2 35 2 10 2
Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of input contains the elements of the tree in the level order form separated by a single space.
If any node does not have a left or right child, take -1 in its place. Refer to the example below.

Example:

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 on its place.

For example, the input for the tree depicted in the below image would be :

alt text

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format :
For each test case, print the Top View of Tree from left to right.

Output for every test case will be printed in a separate line.
Constraint :
1 <= T <= 100
1 <= N <= 1000

Time Limit : 1 sec
Sample Input 1:
 1
 5 35 10 2 3 5 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
2 35 5 10 2
Sample Input 2:
2
5 -1 6 -1 -1
5 6 -1 -1 -1
Sample Output 2:
5 6 
6 5 
Hint

Try to think of which nodes which will be seen if you see a binary tree from above the root and which nodes will be hidden, And which tree traversal should be used.

Approaches (2)
DFS

Before looking at the approach, let's define a couple of terms; the level of a node and the distance of a node. The level of a node means the depth of the node with respect to the root node. So, the level of the root node will be 0, its children's would be 1, and so on. To generalize, if the level of a node is ‘x’, then the level of its children would be ‘x + 1’. 

 

The distance of a node is a measure of how far a node is from the root node in the horizontal direction. It is negative in the left direction and positive in the right direction. For example, the distance for the root node is 0, the distance for root's left child is -1 and for its right child is 1. To generalize, if the distance of a node is ‘x’, then the distance for its left child would be ‘x - 1’ and for its right child would be ‘x + 1’.

 

The following image will give an example of a tree with the level and distance of all nodes marked in the format ('distance', ‘level’)

 

Illustration to show level and distance of nodes

 

 

  1. We will be doing a depth-first search. An edge case would be when the root is null. in that case we will simply return without doing anything
  2. The main idea is that let’s say the root is at a distance 0 and if we go towards its right, child distance should be increased by 1 for the right child and distance should be decreased by 1 if we go towards the left child.
  3. It should be noted that if you see from the top you will be able to see only those nodes which come first at a distance from the root and others will get hidden by these. So we need to know the distance and level of a node from the root.
  4. To store distance and level of a node we will maintain a hashmap.
  5. Now start DFS from the root with its level 0 and distance 0 from the root. If the distance of this node from the root is not present in the hashmap simply add a pair of node value and level of this node at the present distance of the given node. Else if there is a node at a distance then we will be able to see which is at a lower level so compare the level of the current node and the node present at this distance from the hashmap. If the current node is at a lower level, update the hashmap at the current distance with current node value and it’s level.
  6. Now since we will be using an ordered-map or any tree-based map which keeps the key sorted so if we traverse the hashmap leftmost distance will come first so traverse the map and print the node value which is stored in the hashmap.
Time Complexity

O(N * log(N)), where N is the number of nodes in the given binary tree

 

As every node is visited once. with each insertion operation in Map requiring O(log(N)) complexity.

Space Complexity

O(N), where N is the number of nodes in the given binary tree

 

In the worst case we will be storing the distance of every node in the hashmap.

Code Solution
(100% EXP penalty)
Top View
All tags
Sort by
Search icon

Interview problems

Template error solved & Easiest Solution

//Write your code inside this function 
//void printTopView(BinaryTreeNode<int> *root) 

#include<bits/stdc++.h>

void solve(map<int, pair<int, int>>&m, BinaryTreeNode<int> *root, int hd, int level){
    if (root==NULL){
        return;
    }
    if(m.find(hd) == m.end() || m[hd].second > level){
        m[hd] = {root->data, level};
    }
    solve(m, root->left, hd-1, level+1);
    solve(m, root->right, hd+1, level+1);
}


void printTopView(BinaryTreeNode<int> *root) 
{
    map<int, pair<int,int>>m;
    solve(m, root, 0, 0);
    for(auto i:m){
        cout<<i.second.first<<" ";
    }
}
58 views
1 reply
0 upvotes

Interview problems

Working JAVA solution (NO NEED TO CREATE TREE):

import java.util.*;

 

class Pair

{   

    BinaryTreeNode node;

    int vertical_pos;

    Pair( BinaryTreeNode node,int vertical_pos) 

    {

        this.vertical_pos = vertical_pos;

        this.node = node;

    }

}

public class Solution 

{

    public static void printTopView(BinaryTreeNode<Integer> root)

    {

        if(root!=null)

        {

        Map<Integer,Integer> hmap = new TreeMap<>();

        Queue<Pair> queue = new LinkedList<>();

        queue.add(new Pair(root,0));

        while(!queue.isEmpty())

        {

            Pair p = queue.remove();

            BinaryTreeNode node = p.node;

            int vertical_pos = p.vertical_pos;

            

            if(!hmap.containsKey(vertical_pos))

                hmap.put(vertical_pos,(Integer)node.data);

            

            if(node.left!=null)

            {

                queue.add(new Pair(node.left,vertical_pos-1));

            } 

            if(node.right!=null)

            {

                queue.add(new Pair(node.right,vertical_pos+1));

            } 

        }

        for(int values:hmap.values())

            System.out.print(values+" ");

        }

    }

}

27 views
0 replies
0 upvotes

Interview problems

Correct code : printTopView function is missing .If you add your logic inside printTopView(BinaryTreeNode<int>* root ){} it will work fine.

This is the correct code :  #include<bits/stdc++.h>

using namespace std ; 

 

  

 // for creating the tree levelwise from the given string format

BinaryTreeNode<int>*  levelBuildTree(string s  ){

    int n =s.length(); 

    // null node case handle 

 

    int index =0 ; 

    BinaryTreeNode<int>* root = NULL ; 

    

    int value = s[index]-'0' ; 

    if (value ==-1 ){

        return NULL ;

    }

    else if (value !=-1 ){

        root = new BinaryTreeNode<int>(value); 

        index +=2 ;

    }

 

    queue<BinaryTreeNode<int>* > q; 

    q.push(root); 

 

    while (!q.empty() and index< n ){

        BinaryTreeNode<int>* temp =q.front(); 

        q.pop(); 

        int leftData = s[index ]-'0';

        if (leftData!=-1 ){

            temp->left =new BinaryTreeNode<int>(leftData   ); 

            index+=2 ;

            q.push(temp->left );

        } 

        else{

            temp->left = NULL ;

        }

 

        int rightData = s[index ]-'0';

        if (rightData!=-1 ){

            temp->right =new BinaryTreeNode<int>(rightData   ); 

            index+=2 ;

            q.push(temp->right );

        } 

        else{

            temp->right=NULL ;

        }

 

        

     

 

    }

 

    return root ;

 

}

 

// for printing the top view of the binary tree (MAIN LOGIC )

void  printTopView (BinaryTreeNode<int>* root ){

    vector<int>ans;

    if (!root )return ;

 

    map<int , int > nodes ; // 1 to one mapping 

    queue<pair<BinaryTreeNode<int>* , int>> q ; 

 

    q.push(make_pair(root , 0 )); 

 

    while (!q.empty()){

        int n = q.size() ; 

 

        for (int i=0 ;i<n;i++){

            pair<BinaryTreeNode<int>* , int>frontValue= q.front() ;

            q.pop(); 

            BinaryTreeNode<int>* frontNode = frontValue.first ; 

            int hd = frontValue.second ; 

 

            if (nodes.find(hd)== nodes.end()){

                nodes[hd] = frontNode->data ;

            }

 

            if (frontNode->left){

                q.push(make_pair(frontNode->left , hd-1 ));

            }

 

            if(frontNode->right){

                q.push(make_pair(frontNode->right, hd+1 ));

            }

            

        }

    }

 

    for (auto i: nodes){

        cout<<i.second<<" ";

    }

 

    cout<<endl;

}

 // given input string format to tree creation

int uniqueSubstrings(string input)

{

    //Step 1 :  level order to binary tree creation 

    int index =0 ; 

    BinaryTreeNode<int>* root = levelBuildTree(input);

 

    // step2 : find the topview of the binary tree 

 

    if (!root ){

       

        cout<< "-1" ; 

         return 1; 

    }

 

    printTopView(root);

    return 1;

 

}

 

83 views
0 replies
0 upvotes

Interview problems

Java code

import java.util.*;

 

public class Solution 

{

    public static void printTopView(BinaryTreeNode<Integer> root) {

        Queue<Tree> queue = new LinkedList<>();

        TreeMap<Integer, Integer> map = new TreeMap<>();

        if(root != null) {

            int x = 0;

            int y = 0;

            queue.offer(new Tree(x, y, root));

        }

 

        while(queue.size() != 0) {

            Tree tree = queue.poll();

            if(tree.node.left != null) {

                int updatedX = tree.x + 1;

                int updatedY = tree.y - 1;

                queue.offer(new Tree(updatedX, updatedY, tree.node.left));

            }

            if(tree.node.right != null) {

                int updatedX = tree.x + 1;

                int updatedY = tree.y + 1;

                queue.offer(new Tree(updatedX, updatedY, tree.node.right));

            }

 

            if(!map.containsKey(tree.y)) {

                map.put(tree.y, tree.node.data);

            }

        }

        for(Map.Entry<Integer, Integer> m : map.entrySet()) {

            System.out.print(m.getValue());

            System.out.print("\t");

        }

 

    }

}

 

class Tree {

    int x;

    int y;

    BinaryTreeNode<Integer> node;

    public Tree(int x, int y, BinaryTreeNode<Integer> node) {

        this.x = x;

        this.y = y;

        this.node = node;

    }

}

62 views
0 replies
0 upvotes

Interview problems

Wrong Default Code

Problem: Top View int uniqueSubstrings(string input){

    //Write your code here

} Where is the tree?  

63 views
0 replies
0 upvotes

Interview problems

BUG

You need to  import printTopView

23 views
0 replies
0 upvotes

Interview problems

Use this template to try this question

void printTopView(BinaryTreeNode<int> *root) 

{

 }

 

122 views
0 replies
1 upvote

Interview problems

bug

the fucnction isnt callable and we are not getting output because of wrong driver code and input

59 views
0 replies
0 upvotes

Interview problems

What is this ? is the question wrong or me?

Top View

82 views
2 replies
0 upvotes

Interview problems

Discussion thread on Interview Problem | Top View

Hey everyone, creating this thread to discuss the interview problem - Top View.

 

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Top View

 

185 views
2 replies
0 upvotes
Full screen
Console