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.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

Sort by

recency

|

966 Discussions

|

  • hackerrank4290
     + 0 comments

    This problem is simply not well defined. "the set of nodes visible when the tree is viewed from the top" is meaningless. There is no "top" though I suppose they mean "root". Similarly "viewed" simply does not mean anything in this context.

  • pedroramoscunha1
     + 0 comments

    Hi, I'm having an issue to run the code i did in this exercise. I tested on my machine and it worked as expected. But for some reason, the test here does not output any value. Am I doing something wrong?

    def topView(root):
    left_wing = ''
    right_wing = ''
    if(root.left is not None):
        left_wing = topView(root.left)
    if(root.right is not None):
        right_wing = topView(root.right)
        
    ''' return value if is a leaf '''
    if((root.left is None) & (root.right is None)):
        return str(root.info)
    ''' If it has only the right side '''
    if(left_wing == ''):
        return str(root.info) +' '+ right_wing
    ''' If it has only the left side '''
    if(right_wing == ''):
        return str(root.info) +' '+ left_wing
    ''' Else then check between both wings'''
    rw_max = int((right_wing.split(' '))[-1])
    lw_max = int((left_wing.split(' '))[-1])
    
    if(rw_max>=lw_max):
        return str(root.info) +' '+ right_wing
    else:
        return str(root.info) +' '+ left_wing

  • ms_salvemini
     + 0 comments

    I try to find a better definition of top view since the one presented is terrible: the list nodes, from left to the right, that projected vertically from the top to the bottom, are NOT covered by other nodes. 

    # layer: meant as horizontal layer, integer
#    < 0 (left of the root) or > 0 (right of the root)
# depth: depth in the three from zero, always positive

def explore(node, results, layer: int = 0, depth : int = 0):
    if layer not in results:
        # if it a new layer, no matter of the current depth
        results[layer] = { 'depth': depth, 'content': node.info }
    else:
        # there was already a node on this layer
        if depth < results[layer].get('depth'):
            results[layer] = { 'depth': depth, 'content': node.info }
    
    if node.left is not None:
        explore(node.left, results, layer-1, depth+1)
       
    if node.right is not None:
        explore(node.right, results, layer+1, depth+1)
    
def topView(root):
    #Write your code here
    results = {}
    explore(root, results)

    min_index = min(results.keys())
    max_index = max(results.keys())
    for i in range(min_index, max_index+1):
        print(results[i].get('content'), end=" ")

  • berkeragir
     + 0 comments

    The definition of top view is not clear at all. There should be at least two examples with expected output to help understand a better description.

  • mdsanz
     + 0 comments

    My Java 8 Solution

    public static void topView(Node root) {
      if (root == null) {
        return;
      }
      
      class Pair {
        Node node;
        int hd;
        
        Pair(Node n, int h) {
            node = n;
            hd = h;
        }
      }
      
      Map<Integer, Integer> topViewMap = new TreeMap<>();
      Queue<Pair> queue = new LinkedList<>();
      queue.add(new Pair(root, 0));
      
      while (!queue.isEmpty()) {
        Pair current = queue.poll();
        Node currentNode = current.node;
        int hd = current.hd;
        
        if (!topViewMap.containsKey(hd)) {
            topViewMap.put(hd, currentNode.data);
        }
        
        if (currentNode.left != null) {
            queue.add(new Pair(currentNode.left, hd - 1));
        }
        
        if (currentNode.right != null) {
            queue.add(new Pair(currentNode.right, hd + 1));
        }
      }
      
      for (int value : topViewMap.values()) {
        System.out.print(value + " ");
      }
    }