Top View of Binary Tree in DSA Python - Build from Scratch

Top View of Binary Tree

📖 Scenario: You are working with a binary tree data structure. You want to find the top view of the tree. The top view means the nodes visible when you look at the tree from above, ignoring nodes hidden behind others.Imagine standing above a park with tall trees. You want to see only the tallest tree at each position from left to right. Similarly, in a binary tree, the top view shows the first node at each horizontal distance from the root.

🎯 Goal: Build a program that creates a binary tree, then finds and prints the top view of the tree from left to right.

📋 What You'll Learn

Create a binary tree with given nodes and structure

Use a variable to track horizontal distances from the root

Implement logic to find the top view nodes using level order traversal

Print the top view nodes in order from leftmost to rightmost

💡 Why This Matters

🌍 Real World

Top view of a binary tree is useful in computer graphics, network routing, and understanding hierarchical data from a different perspective.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree Nodes

Create a class called Node with an __init__ method that takes data, left, and right parameters. Initialize self.data, self.left, and self.right accordingly. Then create the root node with data = 1, its left child with data = 2, and right child with data = 3. Also create left child of node 2 with data = 4 and right child of node 2 with data = 5.

DSA Python

# Define Node class and create the binary tree nodes
# Your code here

Hint

Define the Node class first. Then create the root and its children exactly as described.

2

Set Up a Dictionary to Track Horizontal Distances

Create an empty dictionary called top_view_map to store the first node data seen at each horizontal distance. Also create a queue called queue and add a tuple with the root node and horizontal distance 0: (root, 0).

DSA Python

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Create top_view_map dictionary and queue with (root, 0)
# Your code here

Hint

Use a dictionary to store horizontal distances as keys and node data as values. Use a list as a queue starting with the root and distance 0.

3

Implement the Top View Logic Using Level Order Traversal

Use a while loop that runs while queue is not empty. Inside the loop, pop the first element from queue into node and hd (horizontal distance). If hd is not in top_view_map, add node.data to top_view_map[hd]. If node.left exists, append (node.left, hd - 1) to queue. If node.right exists, append (node.right, hd + 1) to queue.

DSA Python

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

top_view_map = {}
queue = [(root, 0)]

# Implement the while loop to fill top_view_map
# Your code here

Hint

Use a queue to do level order traversal. Track horizontal distance and add the first node at each distance to the map.

4

Print the Top View Nodes from Left to Right

Print the values in top_view_map sorted by their horizontal distance keys. Use print([top_view_map[hd] for hd in sorted(top_view_map)]).

DSA Python

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

top_view_map = {}
queue = [(root, 0)]

while queue:
    node, hd = queue.pop(0)
    if hd not in top_view_map:
        top_view_map[hd] = node.data
    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
# Your code here

Hint

Sort the keys of top_view_map and print the corresponding node data in a list.

Practice

1. What does the top view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the right side

B. Nodes visible when the tree is viewed from the left side

C. All leaf nodes of the tree

D. Nodes visible when the tree is viewed from above

Solution

1. Step 1: Understand the meaning of top view

   The top view of a binary tree shows nodes that are visible when looking down vertically from above the tree.

2. Step 2: Compare with other views

   Left or right views show nodes visible from sides, and leaf nodes are only the bottom nodes, so they are different.

3. Final Answer:

   Nodes visible when the tree is viewed from above -> Option D

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view means looking down from above the tree [OK]

Common Mistakes:

• Confusing top view with left or right view
• Thinking top view shows all leaf nodes
• Assuming top view includes all nodes

2. Which of the following Python data structures is best suited to store nodes by their horizontal distance for top view calculation?

easy

A. Set

B. List

C. Dictionary

D. Tuple

Solution

1. Step 1: Identify the need for key-value mapping

   We need to map horizontal distances (keys) to nodes (values) to track the first node at each horizontal distance.

2. Step 2: Choose the appropriate data structure

   Dictionaries provide key-value pairs, allowing efficient lookup and insertion by horizontal distance.

3. Final Answer:

   Dictionary -> Option C

4. Quick Check:

   Use dictionary for horizontal distance mapping [OK]

Hint: Use dictionary to map horizontal distance to nodes [OK]

Common Mistakes:

• Using list which is index-based, not key-based
• Using set which stores unique values without keys
• Using tuple which is immutable and not key-value

3. Consider the following binary tree:

        1
       / \
      2   3
       \   \
        4   5

What is the top view of this tree?

medium

A. [2, 1, 3, 5]

B. [1, 2, 4, 5]

C. [2, 1, 3]

D. [1, 4, 5]

Solution

1. Step 1: Assign horizontal distances

   Root (1) is at 0, left child (2) at -1, right child (3) at +1, node 4 at 0 (right of 2), node 5 at +2 (right of 3).

2. Step 2: Select first nodes at each horizontal distance

   At -1: 2, at 0: 1 (4 is below 1), at +1: 3, at +2: 5.

3. Final Answer:

   [2, 1, 3, 5] -> Option A

4. Quick Check:

   Top view nodes by horizontal distance = [2,1,3,5] [OK]

Hint: Pick first node at each horizontal distance from left to right [OK]

Common Mistakes:

• Including node 4 instead of node 1 at horizontal distance 0
• Missing node 5 at horizontal distance +2
• Confusing order of nodes in output

4. The following code snippet is intended to print the top view of a binary tree but has a bug. What is the error?

from collections import deque

def top_view(root):
    if not root:
        return []
    q = deque([(root, 0)])
    hd_node = {}
    while q:
        node, hd = q.pop()
        if hd not in hd_node:
            hd_node[hd] = node.data
        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))
    return [hd_node[hd] for hd in sorted(hd_node)]

medium

A. Using q.pop() instead of q.popleft() causes wrong traversal order

B. hd_node dictionary is not initialized correctly

C. The horizontal distance is not updated properly

D. The function does not handle empty trees

Solution

1. Step 1: Analyze queue operations

   The code uses deque as a queue but uses q.pop(), which removes from the right (stack behavior), not from the left (queue behavior).

2. Step 2: Understand traversal order impact

   Top view requires level order traversal (BFS), so nodes must be processed in FIFO order using q.popleft(). Using pop() reverses order and causes incorrect results.

3. Final Answer:

   Using q.pop() instead of q.popleft() causes wrong traversal order -> Option A

4. Quick Check:

   Use popleft() for BFS queue traversal [OK]

Hint: Use popleft() for BFS, pop() is for stack (LIFO) [OK]

Common Mistakes:

• Confusing pop() with popleft() in deque
• Not realizing BFS needs FIFO order
• Thinking dictionary initialization is the problem

5. Given a binary tree where multiple nodes share the same horizontal distance and level, which node should be included in the top view?

hard

A. The node with the maximum value at that horizontal distance

B. The node that appears first in level order traversal at that horizontal distance

C. The node that appears last in level order traversal at that horizontal distance

D. All nodes at that horizontal distance

Solution

1. Step 1: Understand top view node selection

   Top view includes the first node encountered at each horizontal distance during level order traversal (BFS), which means the node closest to the root vertically.

2. Step 2: Eliminate other options

   Maximum value or last node in traversal is not considered; all nodes at same horizontal distance are not included, only the first one.

3. Final Answer:

   The node that appears first in level order traversal at that horizontal distance -> Option B

4. Quick Check:

   Top view = first node at horizontal distance in BFS [OK]

Hint: Pick first node at horizontal distance in BFS order [OK]

Common Mistakes:

• Choosing node by value instead of position
• Including all nodes at same horizontal distance
• Picking last node instead of first in BFS