Source Code:

Solution:

– We’ll take verticle height of each node. For root it’s 0 & if height – 1, if we’re going right & height + 1, if we’re going left

– Take Queue & add root node into it

– Now one by one remove item from queue & add into Tree map based on height as key. Add only key is not present in map

– Do it until queue is empty

– At last, print all values of map

– Time Complexity: O(n)

– Space Complexity: O(n)

Please…

While solving the problem on some platforms, height cannot be added as a parameter in node class, what to do then.

Simplest explanation on internet. wow..

What is the space complexity of this code? O(N) or something else?

duplicates in binary search tree are not allowed.

Excellent Solution

Fantastic! This is basically a variation of level order traversal, right?

why use LinkedList in Queue object?

hi sir, Can i solve in this manner ? It is giving correct answer. Please suggest is it a right approach ?

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

static void getTopView(Node root,int level){

if (root==null) {

return ;

}

if(!map.containsKey(level)){

map.put(level,root.data);

}

getTopView(root.right,level+1);

getTopView(root.left,level-1);

}

Complexity of adding n elements in TreeMap is O(nlogn) . so time complexity should be O(nlogn)

Great video. Thankyou for the awesome explanation Sir.

Perfect Explanation. Thanks coding simplified.

how the height is calculated automatically without any function….how .height calculate the height ?

Sir, I have tried the way from your video of vertical order traversal.

I remove the code where we have the key in the map,the idea is that to only get numbers whose level is not considered but is wrong I am not able to understand why?

public void getVerticalOrder(Node node, int hd, TreeMap<Integer, ArrayList<Integer>> m) {

if (node == null) {

return;

}

if (m.get(hd) == null) {

ArrayList<Integer> l = new ArrayList<Integer>();

l.add(node.data);

m.put(hd, l);

}

getVerticalOrder(node.left, hd – 1, m);

getVerticalOrder(node.right, hd + 1, m);

Line number 28…. What will get stored in hd variable for root Node? 0?

thanks!

please provide the source code of all the questions in description

This can also work..

Set<Integer> a= new HashSet<>();

void TopView(Node root, int level){

if(root==null)return;

if(!a.contains(level))

{

System.out.print(" "+root.data+" ");

a.add(level);

}

TopView(root.left, level-1);

TopView(root.right, level+1);

}

I think height variable in Node represents the distance from the root, so better to rename it distance.

Plzz help…

This approach does not require a queue. Here we use the two variables, one for vertical distance of current node from the root and another for the depth of the current node from the root. We use the vertical distance for indexing. If one node with the same vertical distance comes again, we check if depth of new node is lower or higher with respect to the current node with same vertical distance in the map. If depth of new node is lower, then we replace it.

This is from geeksforgeeks..

Why do we need to check the level of the node..Cant we just put the first element with the same horizontal distance in the top view of the tree..

Plzzzzzzzzzz HElppppppppppppp

Best explanation on whole internet..You have really explained what the top level actually means..Thanks Sir..Please carry on ..