Top View of Binary Tree in DSA Python - Execution Trace

Concept Flow - Top View of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for level order traversal

↓

Pop node from queue

↓

Check if horizontal distance seen before?

↓

Add node to top view map

↓

Add left child with hd-1 to queue

↓

Add right child with hd+1 to queue

↓

Repeat until queue empty

↓

Sort top view map by horizontal distance

↓

Print nodes in sorted order

↓

Done

Traverse the tree level by level, track horizontal distances, record first node at each distance for top view.

Execution Sample

DSA Python

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

Prints the top view nodes of a binary tree by horizontal distance using level order traversal.

Execution Table

Step	Operation	Node Visited (Value)	Horizontal Distance (hd)	Top View Map (hd: node)	Queue State	Visual State
1	Start with root	1	0	{}	[(1,0)]	Tree root at hd=0
2	Pop from queue	1	0	{0:1}	[]	Top view map updated with root
3	Add left child	2	-1	{0:1}	[(2,-1)]	Left child at hd=-1 added
4	Add right child	3	1	{0:1}	[(2,-1),(3,1)]	Right child at hd=1 added
5	Pop from queue	2	-1	{0:1,-1:2}	[(3,1)]	Top view map updated with left child
6	Add left child	4	-2	{0:1,-1:2}	[(3,1),(4,-2)]	Left child of 2 at hd=-2 added
7	Add right child	5	0	{0:1,-1:2}	[(3,1),(4,-2),(5,0)]	Right child of 2 at hd=0 added but hd=0 already in map
8	Pop from queue	3	1	{0:1,-1:2,1:3}	[(4,-2),(5,0)]	Top view map updated with right child
9	Add right child	6	2	{0:1,-1:2,1:3}	[(4,-2),(5,0),(6,2)]	Right child of 3 at hd=2 added
10	Pop from queue	4	-2	{0:1,-1:2,1:3,-2:4}	[(5,0),(6,2)]	Top view map updated with left child of 2
11	Pop from queue	5	0	{0:1,-1:2,1:3,-2:4}	[(6,2)]	hd=0 already in map, no update
12	Pop from queue	6	2	{0:1,-1:2,1:3,-2:4,2:6}	[]	Top view map updated with right child of 3
13	Queue empty	None	None	{-2:4,-1:2,0:1,1:3,2:6}	[]	Traversal complete, top view map ready
14	Print top view	N/A	N/A	N/A	N/A	Print nodes in order: 4 2 1 3 6

💡 Queue is empty, all nodes processed, top view map complete

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 10	After Step 12	Final
queue	[(1,0)]	[]	[(3,1)]	[(4,-2),(5,0)]	[(5,0),(6,2)]	[]	[]
top_nodes	{}	{0:1}	{0:1,-1:2}	{0:1,-1:2,1:3}	{0:1,-1:2,1:3,-2:4}	{0:1,-1:2,1:3,-2:4,2:6}	{-2:4,-1:2,0:1,1:3,2:6}
node	1	1	2	3	4	6	N/A
hd	0	0	-1	1	-2	2	N/A

Key Moments - 3 Insights

Why do we only add a node to the top view map if its horizontal distance is not already present?

Because the top view shows the first node visible at each horizontal distance from the top. Later nodes at the same horizontal distance are hidden behind earlier ones. See execution_table rows 2, 7, and 11 where hd=0 is already in the map, so new nodes at hd=0 are ignored.

Why do we use a queue and level order traversal instead of depth-first traversal?

Level order traversal ensures we visit nodes top-down, left to right at each level. This way, the first node encountered at each horizontal distance is the topmost visible node. See concept_flow and execution_table steps showing queue usage.

What does the horizontal distance represent and how is it updated?

Horizontal distance (hd) measures how far left or right a node is from the root (hd=0). Left child has hd-1, right child hd+1. This helps group nodes vertically for the top view. See variable_tracker and concept_flow for hd updates.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, why is the node with value 5 not added to the top view map?

A Because its horizontal distance 0 is already in the map

B Because it has no children

C Because the queue is empty

D Because it is a right child

💡 Hint

Check the 'Top View Map' column at step 7 in execution_table

At which step does the horizontal distance -2 first appear in the top view map?

A Step 6

B Step 10

C Step 4

D Step 12

💡 Hint

Look at the 'Top View Map' column and find when hd=-2 is added

If the node with value 6 had a left child, what would happen to the queue after step 12?

A The left child would be added with hd=1

B The left child would be added with hd=3

C The left child would be added with hd=2

D No child would be added

💡 Hint

Recall left child hd = parent hd - 1; see concept_flow for hd updates

Concept Snapshot

Top View of Binary Tree:
- Use level order traversal with a queue
- Track horizontal distance (hd) for each node
- Record first node at each hd in a map
- Left child hd = hd - 1, right child hd = hd + 1
- After traversal, print nodes sorted by hd
- Shows nodes visible from top, ignoring hidden ones

Full Transcript

The top view of a binary tree shows nodes visible when looking from above. We start at the root with horizontal distance zero. Using a queue, we traverse level by level. For each node, if its horizontal distance is not yet recorded, we add it to the top view map. We add left and right children to the queue with updated horizontal distances. This ensures the first node at each horizontal distance is recorded, representing the top view. After traversal, we print nodes sorted by horizontal distance. This method uses level order traversal to capture the topmost nodes at each vertical line.

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