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

Tree : Top View

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • vikram_viky2001
    3 months 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
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy