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

|

957 Discussions

|

  • CS_2212256_T
     + 0 comments

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

    }

    Queue> queue = new LinkedList<>(); // Map to store the first node at each horizontal distance Map map = new TreeMap<>();

        // Start with the root node and horizontal distance 0
    queue.offer(new AbstractMap.SimpleEntry<>(root, 0));

    while (!queue.isEmpty()) {
        Map.Entry<Node, Integer> entry = queue.poll();
        Node node = entry.getKey();
        int horizontalDistance = entry.getValue();

        // If the horizontal distance is not yet in the map, add it
        if (!map.containsKey(horizontalDistance)) {
            map.put(horizontalDistance, node.data);
        }

        // If the node has a left child, enqueue it with horizontal distance - 1
        if (node.left != null) {
            queue.offer(new AbstractMap.SimpleEntry<>(node.left, horizontalDistance - 1));
        }

        // If the node has a right child, enqueue it with horizontal distance + 1
        if (node.right != null) {
            queue.offer(new AbstractMap.SimpleEntry<>(node.right, horizontalDistance + 1));
        }
    }

    // Print the top view by iterating over the map
    for (int value : map.values()) {
        System.out.print(value + " ");
    }
}

  • saibhossain5
     + 0 comments

    from collections import deque def topView(root): if(root==None): return 0 hd_map = {}

    queue = deque([(root, 0)])

while queue:
    node, hd = queue.popleft()
    if hd not in hd_map:
        hd_map[hd] = node.info

    if node.left:
        queue.append((node.left, hd - 1))
    if node.right:
        queue.append((node.right, hd + 1))
print(" ".join(str(hd_map[hd]) for hd in sorted(hd_map)))

  • ankithkumar6281
     + 0 comments

    DFs:

    public static void top(Node root,Map m,int w,int h){

        if(root == null) return;

    if(!m.containsKey(w))  
        m.put(w, new int[]{h,root.data});
    else if(m.get(w)[0] > h)
        m.put(w, new int[]{h,root.data});

    top(root.left, m,w-1,h+1);
    top(root.right, m, w+1,h+1);

    }

    public static void topView(Node root) {

        Map<Integer,int[]> m = new TreeMap<Integer,int[]>();
    top(root,m,0,0);
    for(int k : m.keySet()){
        System.out.print(m.get(k)[1] + " ");
    }
}

  • 2k23_cscys231212
     + 0 comments
    /*
class Node {
    public:
        int data;
        Node *left;
        Node *right;
        Node(int d) {
            data = d;
            left = NULL;
            right = NULL;
        }
};

*/

   void topView(Node* root) {
    if (!root) return;
    queue<pair<Node*, int>> q;
    map<int, int> mp;
    q.push({ root, 0 });
    while (q.size()) {
        auto temp = q.front();
        q.pop();
        int horizontal_distance = temp.second;
        Node* node = temp.first;
        if (!mp[horizontal_distance]) {
            mp[horizontal_distance] = node->data;
        }
        if (node->left) {
            q.push({ node->left, horizontal_distance - 1 });
        }
        if (node->right) {
            q.push({ node->right, horizontal_distance + 1 });
        }
    }
    for (auto node : mp) {
        cout << node.second << ' ';
    }
}

  • arunavobiswas18
     + 0 comments

    By top view does it mean by top view? From provided example it looks like it traversed only right child only, and the there was no left child in the sample input and output provided. So in case of presence of left child to root will it also traverse left childrens too. In any case I wrote the following java code for traversing left chilrens and right childrens from root and seems to work for base testcase:

    public static void topView(Node root) {
      List<Integer> ar = new ArrayList<Integer>();
      //start at root
      Node cur = root;
      ar.add(cur.data);
      //traverse all left children
      while(cur.left!=null){
          cur = cur.left;
          ar.add(cur.data);
      }
      
      cur = root;
      //traverse all right children
      while(cur.right!=null){
          cur = cur.right;
          ar.add(cur.data);
      }
      
      for(int i:ar){
          System.out.print(i+" ");
      }
      
    }

    Please suggest improvements to this code. Thanks