Top View of Binary Tree in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new node in the binary tree.

DSA Python

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

root = Node([1])

Drag options to blanks, or click blank then click option'

A0

BNone

Croot

D10

Attempts:

3 left

💡 Hint

Common Mistakes

Using None instead of a value for the root node.

Using a variable name instead of a value.

The root node should be initialized with the value 10 to create the binary tree's root.

2fill in blank

medium

Complete the code to insert a node to the left of the root.

DSA Python

root.left = Node([1])

Drag options to blanks, or click blank then click option'

A5

BNone

C20

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning None instead of a node.

Assigning the root node itself.

The left child of the root is assigned a new node with value 5.

3fill in blank

hard

Fix the error in the function to print the top view of the binary tree.

DSA Python

def top_view(root):
    if root is None:
        return
    queue = [(root, 0)]
    top_nodes = {}
    while queue:
        node, hd = queue.pop(0)
        if hd not in top_nodes:
            top_nodes[[1]] = node.data
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    for key in sorted(top_nodes):
        print(top_nodes[key], end=' ')

Drag options to blanks, or click blank then click option'

Anode

Bhd

Cqueue

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using the node object as a key instead of horizontal distance.

Using the queue or root as a key.

The horizontal distance (hd) is used as the key to store the first node at that distance.

4fill in blank

hard

Fill both blanks to complete the code that builds the top view dictionary.

DSA Python

def top_view(root):
    if root is None:
        return
    queue = [(root, 0)]
    top_nodes = {}
    while queue:
        node, hd = queue.pop(0)
        if [1] not in top_nodes:
            top_nodes[[2]] = node.data
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))

Drag options to blanks, or click blank then click option'

Ahd

Bnode

Cqueue

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for the key in the dictionary.

Using node or queue as keys.

Both blanks should be the horizontal distance 'hd' to correctly track nodes by their horizontal distance.

5fill in blank

hard

Fill all three blanks to complete the code that prints the top view nodes in order.

DSA Python

def top_view(root):
    if root is None:
        return
    queue = [(root, 0)]
    top_nodes = {}
    while queue:
        node, hd = queue.pop(0)
        if hd not in top_nodes:
            top_nodes[hd] = node.data
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    for key in [1](top_nodes):
        print(top_nodes[[2]], end=[3])

Drag options to blanks, or click blank then click option'

Asorted

Bkey

C' '

Dtop_nodes

Attempts:

3 left

💡 Hint

Common Mistakes

Not sorting the keys before printing.

Using wrong variable names to access dictionary.

Printing without spaces.

We sort the keys to print nodes from left to right, use 'key' to access values, and print with a space separator.

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