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.
IMHO, key points are :
- use a level order traversal (needs a queue, e.g. ArrayDeque)
- keep track of nodes' horizontal distance along nodes (any kind of Pair-like types will help. Use FQN when import are needed, since you cannot edit them)
- given an horizontal distance value, store the first node.data value encountered only into a map
- keep your map ordered by horizontal distance (TreeMap will help)
Here's my Java solution :
publicstaticvoidtopView(Noderoot){Map<Integer,Integer>topView=newTreeMap<>();// TreeMap to keep it sorted by keysQueue<java.util.AbstractMap.SimpleEntry<Integer,Node>>queue=newArrayDeque<>();queue.add(newjava.util.AbstractMap.SimpleEntry<Integer,Node>(0,root));topView.put(0,root.data);while(!queue.isEmpty()){java.util.AbstractMap.SimpleEntry<Integer,Node>currentEntry=queue.poll();IntegerhorizontalDistance=currentEntry.getKey();NodecurrentNode=currentEntry.getValue();topView.putIfAbsent(horizontalDistance,currentNode.data);if(currentNode.left!=null)queue.add(newjava.util.AbstractMap.SimpleEntry<>(horizontalDistance-1,currentNode.left));if(currentNode.right!=null)queue.add(newjava.util.AbstractMap.SimpleEntry<>(horizontalDistance+1,currentNode.right));}for(inthd:topView.keySet()){System.out.print(topView.get(hd)+" ");}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tree : Top View
You are viewing a single comment's thread. Return to all comments →
IMHO, key points are : - use a level order traversal (needs a queue, e.g. ArrayDeque) - keep track of nodes' horizontal distance along nodes (any kind of Pair-like types will help. Use FQN when import are needed, since you cannot edit them) - given an horizontal distance value, store the first node.data value encountered only into a map - keep your map ordered by horizontal distance (TreeMap will help)
Here's my Java solution :