We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Note: testcases have been changed for this problem. Hence, the prev. approach shown in popular comments doesn't work.
I'm implementing the tree node with an extra variable called 'node level'.
An example of the new tree looks like this:
Here's my code with suitable comments in Java
//new class to store level of each node along with the node staticclassQueueNode{Nodenode;intlevel;publicQueueNode(Nodenode,intlevel){this.node=node;this.level=level;}}publicstaticvoidtopView(Noderoot){//took a queue - similar to BFS approachQueue<QueueNode>queue=newLinkedList<QueueNode>();//Taking a TreeMap<first, second>//first - stores the level of the node//second - stores the node.dataTreeMap<Integer,Integer>map=newTreeMap<Integer,Integer>();//why TreeMap? Because I want the nodes to be sorted from leftmost to rightmost//start (since root, level = 0)queue.add(newQueueNode(root,0));while(!queue.isEmpty()){//remove element from queueQueueNoder=queue.poll();//if the level of this node has never been reached before -> visible in top viewif(!map.containsKey(r.level)){map.put(r.level,r.node.data);}//add node's descendants//all left child node levels = node.level - 1//all right child node levels = node.level + 1if(r.node.left!=null){queue.add(newQueueNode(r.node.left,r.level-1));}if(r.node.right!=null){queue.add(newQueueNode(r.node.right,r.level+1));}}//since already sorted (cuz TreeMap), print from left to rightfor(Integervalue:map.values()){System.out.print(value+" ");}}
Tree : Top View
You are viewing a single comment's thread. Return to all comments →
Solution Explained (With code)
Note: testcases have been changed for this problem. Hence, the prev. approach shown in popular comments doesn't work.
I'm implementing the tree node with an extra variable called 'node level'. An example of the new tree looks like this:
Here's my code with suitable comments in Java
I've written a blog post about this problem here: Trees: Top View of a Tree
Please upvote this comment if helpful. Thanks! :)