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

|

965 Discussions

|

  • 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 + " ");
      }
    }

  • csaiml1a_2213280
     + 0 comments

    public static void topView(Node root) { if (root == null) return;

    // A class to store node and its horizontal distance (hd)
class QueueNode {
    Node node;
    int hd;

    QueueNode(Node node, int hd) {
        this.node = node;
        this.hd = hd;
    }
}

Queue<QueueNode> queue = new LinkedList<>();
Map<Integer, Integer> topViewMap = new TreeMap<>(); // TreeMap to sort by HD

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

while (!queue.isEmpty()) {
    QueueNode current = queue.poll();
    int hd = current.hd;
    Node node = current.node;

    // Only add to map if this HD hasn't been seen yet
    if (!topViewMap.containsKey(hd)) {
        topViewMap.put(hd, node.data);
    }

    // Enqueue left child with HD-1
    if (node.left != null) {
        queue.add(new QueueNode(node.left, hd - 1));
    }

    // Enqueue right child with HD+1
    if (node.right != null) {
        queue.add(new QueueNode(node.right, hd + 1));
    }
}

// Print the top view in left-to-right order (sorted HD)
for (Map.Entry<Integer, Integer> entry : topViewMap.entrySet()) {
    System.out.print(entry.getValue() + " ");
}

    }