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

|

964 Discussions

|

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

    }

  • remainingphotos1
     + 0 comments

    Here's My Python 3 Code

    Any suggestion to increase efficiency are appreciated please

    def topView(root):
    from collections import deque
    if not root:
        return
    top_nodes = {}
    queue = deque([(root, 0)])
    while queue:
        node, hd = queue.popleft()
        if hd not in top_nodes:
            top_nodes[hd] = node.info
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    for hd in sorted(top_nodes):
        print(top_nodes[hd], end=" ")
    print()