Question

How do you find the top view of a binary tree?

Answer 1

To find the top view of a binary tree, you need to perform a vertical traversal of the tree and record the nodes that are visible from the top. We can use a map or dictionary to store the nodes at each vertical distance from the root. Here's a step-by-step approach to find the top view of a binary tree:

1. Start with the root node and a horizontal distance of 0.
2. Perform a depth-first traversal (pre-order or level order) of the binary tree.
3. At each node, record the node's value in the map or dictionary corresponding to its horizontal distance from the root.
4. If a node is encountered at a horizontal distance that is already in the map, ignore it (since we want the top view).
5. Recur to the left child with a horizontal distance decreased by 1.
6. Recur to the right child with a horizontal distance increased by 1.
7. After traversal, the values stored in the map represent the top view of the binary tree.

Here's a Python-like pseudocode implementation:

def top_view(root):
    if root is None:
        return
    
    # Dictionary to store the top view nodes
    top_view_nodes = {}
    
    # Helper function for vertical traversal
    def vertical_traversal(node, distance):
        if node is None:
            return
        
        # If the current distance is not in the dictionary, add the node
        if distance not in top_view_nodes:
            top_view_nodes[distance] = node.value
        
        # Traverse left with distance decreased by 1
        vertical_traversal(node.left, distance - 1)
        
        # Traverse right with distance increased by 1
        vertical_traversal(node.right, distance + 1)
    
    # Perform vertical traversal starting from the root
    vertical_traversal(root, 0)
    
    # Sort the dictionary by keys (horizontal distance)
    sorted_top_view = sorted(top_view_nodes.items())
    
    # Print the top view nodes
    for distance, value in sorted_top_view:
        print(value, end=' ')
 

You would call this function with the root of the binary tree. It will print the top view nodes of the tree. This algorithm has a time complexity of O(nlogn), where n is the number of nodes in the binary tree, due to sorting the dictionary by keys.