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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 910 Discussions, By:

recency

Please Login in order to post a comment

  • 2101640100219_cs
    2 days ago+ 0 comments

    Time Complexity :- O(n) ------ HashMap

    void topView(Node * root) {
            map<int,int>i;
            queue<pair<Node*,int>>q;q.push({root,500});
            while(!q.empty()){
                pair<Node*,int> t=q.front();q.pop();
                if(t.first->left)q.push({t.first->left,t.second-1});
                if(t.first->right)q.push({t.first->right,t.second+1});
                if(!i[t.second])i[t.second]=t.first->data;
            }
            for(auto k:i)cout<<k.second<<" ";
        }
    
    0|
    Permalink
  • vikram_viky2001
    1 week ago+ 0 comments
    bloc_lst = []
    def blocked_list(root):
        if root is None:
            return
        
        if root.left:
            if root.left.right:
                #print(root.left.right.info,end=" ")
                bloc_lst.append(root.left.right.info)
        
        if root.right:
            if root.right.left:
                #print(root.right.left.info,end=" ")
                bloc_lst.append(root.right.left.info)
        
        blocked_list(root.left)
        blocked_list(root.right)
        
    from collections import defaultdict
    
    def topView(root):
        if not root:
            return
        
        blocked_list(root)
        
        blocked_nodes = bloc_lst
    
        # Create a dictionary to store nodes at each horizontal distance from the root
        hd_map = defaultdict(list)
    
        # Create a queue for level-order traversal
        queue = [(root, 0)]  # Each element is a tuple (node, horizontal distance)
    
        while queue:
            node, hd = queue.pop(0)
    
            # Check if the node is not blocked
            if node.info not in blocked_nodes:
                hd_map[hd].append(node.info)
    
            if node.left:
                queue.append((node.left, hd - 1))
            if node.right:
                queue.append((node.right, hd + 1))
    
        # Print the top view nodes in order of horizontal distance
        for hd in sorted(hd_map):
            print(hd_map[hd][0], end=" ")
    
    0|
    Permalink
  • miss_juliajohn
    3 weeks ago+ 1 comment

    is this right?

    include

    include

    include

    using namespace std;

    struct Node { int data; Node* left; Node* right; };

    void topView(Node* root) { if (root == nullptr) { return; }

    // Create a map to store the horizontal distance and the corresponding node data
    map<int, int> verticalMap;
    
    // Create a queue for level-order traversal
    queue<pair<Node*, int>> levelOrder;
    
    // Initialize the queue with the root and horizontal distance 0
    levelOrder.push({root, 0});
    
    while (!levelOrder.empty()) {
        Node* current = levelOrder.front().first;
        int horizontalDistance = levelOrder.front().second;
        levelOrder.pop();
    
        // If this horizontal distance is not in the map, add it to the map
        if (verticalMap.find(horizontalDistance) == verticalMap.end()) {
            verticalMap[horizontalDistance] = current->data;
        }
    
        // Enqueue the left and right children with updated horizontal distances
        if (current->left != nullptr) {
            levelOrder.push({current->left, horizontalDistance - 1});
        }
        if (current->right != nullptr) {
            levelOrder.push({current->right, horizontalDistance + 1});
        }
    }
    
    // Print the top view from left to right
    for (const auto& entry : verticalMap) {
        cout << entry.second << ' ';
    }
    

    }

    int main() { // Create a sample binary tree and call topView Node* root = new Node{1, new Node{2, nullptr, nullptr}, new Node{3, nullptr, nullptr}}; cout << "Top View of Binary Tree: "; topView(root);

    In this version of the code, I've used a map to store the nodes seen at each horizontal distance, ensuring that only the topmost node at each distance is recorded. This simplifies the code and ensures that it works correctly for various binary tree structures. cout << endl;

    return 0;
    

    }

    0|
    Permalink
  • dehaka
    2 months ago+ 0 comments

    runs in O(n) time, not O(nlog n), no need to search for horizontal level in a map, the checking is done in constant time with the leftside and rightside vectors

    void topView(Node * root) {
            queue<pair<Node*, int>> levelOrder;
            vector<int> leftside = {root->data};
            vector<int> rightside;
            levelOrder.push({root, 0});
            while (!levelOrder.empty()) {
                Node* temp = levelOrder.front().first;
                int currentHorizontal = levelOrder.front().second;
                if (currentHorizontal <=0 and abs(currentHorizontal) == leftside.size()) {
                    leftside.push_back(temp->data);
                } else if (currentHorizontal > 0 and currentHorizontal == rightside.size()+1) {
                    rightside.push_back(temp->data);
                }
                if (temp->left != NULL) {
                    levelOrder.push({temp->left, currentHorizontal-1});
                }
                if (temp->right != NULL) {
                    levelOrder.push({temp->right, currentHorizontal+1});
                }
                levelOrder.pop();
            }
            for (int i=leftside.size()-1; i >= 0; i--) {
                cout << leftside[i] << ' ';
            }
            for (int i=0; i < rightside.size(); i++) {
                cout << rightside[i] << ' ';
            }
        }
    
    0|
    Permalink
  • kdeep05_dg
    2 months ago+ 0 comments
    python 3                                                                                                                       
    def topView(root):                                                                                             
        queue=[]                                                                                                       
        top_view={}                                                                                                   
        queue.append([root,0])                                                                              
        while(queue):                                                                                               
            node,level=queue.pop(0)  # to remove front element                       
            if level not in top_view:                                                                           
                top_view[level]=node.info                                                                                                                     
            if node.left:
                node.left.level=level-1
                queue.append((node.left, level - 1))
            if node.right:
                node.right.level=level+1
                queue.append((node.right, level + 1))
        print(top_view)
        for level in sorted(top_view):
            print(top_view[level],end=" ")
                
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy