Top View of Binary Tree in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top View for a Simple Binary Tree

What is the printed top view of the binary tree after running the given code?

DSA Python

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

def top_view(root):
    if not root:
        return []
    from collections import deque
    q = deque([(root, 0)])
    hd_node = {}
    min_hd = max_hd = 0
    while q:
        node, hd = q.popleft()
        if hd not in hd_node:
            hd_node[hd] = node.val
        min_hd = min(min_hd, hd)
        max_hd = max(max_hd, hd)
        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))
    return [hd_node[i] for i in range(min_hd, max_hd + 1)]

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

print(top_view(root))

A [2, 1, 3]

B [2, 1, 3, 6]

C [2, 1, 4, 5, 6]

D [1, 2, 3, 4, 5, 6]

💡 Hint

Think about horizontal distances and which nodes appear first at each horizontal distance.

The top view prints nodes visible from above. We track horizontal distances (hd) from root (hd=0). Left child decreases hd by 1, right child increases hd by 1. For each hd, the first node encountered in level order is included.

Nodes at hd -1: 2, hd 0: 1, hd 1: 3, hd 2: 6 (since 4 and 5 are hidden behind 2 and 3).

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Top View

In the top view of a binary tree, what does the 'horizontal distance' (hd) represent?

A The vertical level of a node from the root

B The depth of a node in the tree

C The distance of a node from the root measured horizontally, with left child decreasing hd by 1 and right child increasing hd by 1

D The number of nodes between the root and the current node

💡 Hint

Think about how left and right children affect horizontal position.

Horizontal distance is a measure of how far left or right a node is from the root. Left child decreases hd by 1, right child increases hd by 1. This helps identify nodes visible from the top.

🔧 Debug

advanced

Identify the Error in Top View Implementation

What error will this code produce when trying to print the top view of a binary tree?

DSA Python

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(top_view(root))

A IndexError due to empty deque pop

B Correct output: [2, 1, 3]

C KeyError when accessing hd_node

D TypeError due to wrong data type

💡 Hint

Check how nodes are removed from the queue.

The code uses q.pop() which removes from the right end (stack behavior), but nodes are added to the right end. This causes nodes to be processed in reverse order and eventually the queue becomes empty prematurely causing IndexError.

🚀 Application

advanced

Top View of a Complex Binary Tree

Given the binary tree below, what is the top view output? Tree structure: 10 / \ 20 30 / / \ 40 50 60 \ \ 70 80

DSA Python

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

def top_view(root):
    if not root:
        return []
    from collections import deque
    q = deque([(root, 0)])
    hd_node = {}
    min_hd = max_hd = 0
    while q:
        node, hd = q.popleft()
        if hd not in hd_node:
            hd_node[hd] = node.val
        min_hd = min(min_hd, hd)
        max_hd = max(max_hd, hd)
        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))
    return [hd_node[i] for i in range(min_hd, max_hd + 1)]

root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.left = Node(40)
root.left.left.right = Node(70)
root.right.left = Node(50)
root.right.right = Node(60)
root.right.right.right = Node(80)

print(top_view(root))

A [20, 10, 30, 60, 80]

B [40, 20, 10, 30, 50, 60, 80]

C [70, 40, 20, 10, 30, 60, 80]

D [40, 20, 10, 30, 60, 80]

💡 Hint

Remember only the first node at each horizontal distance is visible from the top.

Horizontal distances: 40 at -2, 20 at -1, 10 at 0, 30 at 1, 60 at 2, 80 at 3. Nodes 70 and 50 are hidden behind others at their horizontal distances.

🧠 Conceptual

expert

Why Use Level Order Traversal for Top View?

Why is level order traversal (breadth-first search) preferred when computing the top view of a binary tree?

A Because it processes nodes level by level, ensuring the first node at each horizontal distance is recorded

B Because it only visits leaf nodes

C Because it visits nodes in sorted order of their values

D Because it uses less memory than depth-first search

💡 Hint

Think about which node should be visible from the top at each horizontal distance.

Level order traversal visits nodes level by level from top to bottom. This ensures the first node encountered at each horizontal distance is the topmost node visible from above.

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