Top View of Binary Tree in DSA C - Execution Trace

Concept Flow - Top View of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for level order traversal

↓

For each node dequeued:

↓

Check if horizontal distance

↓

seen before?

↓

If not seen, record node data

↓

Continue until queue empty

↓

Print recorded nodes in order of hd

Traverse the tree level by level, track horizontal distances, record first node at each distance, then print them in order.

Execution Sample

DSA C

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

// Top view uses level order with horizontal distance tracking

This code traverses the binary tree level-wise, tracking horizontal distances to find the top view nodes.

Execution Table

Step	Operation	Node Visited (data)	Horizontal Distance (hd)	Recorded hd nodes	Queue State	Visual Tree State with hd
1	Start at root	1	0	{0:1}	[(1,0)]	1(0)
2	Dequeue node	1	0	{0:1}	[]	1(0)
3	Enqueue left child	2	-1	{0:1}	[(2,-1)]	2(-1) / 1(0)
4	Enqueue right child	3	1	{0:1}	[(2,-1),(3,1)]	2(-1) 3(1) / 1(0)
5	Dequeue node	2	-1	{0:1,-1:2}	[(3,1)]	2(-1) 3(1) / 1(0)
6	Enqueue left child	4	-2	{0:1,-1:2}	[(3,1),(4,-2)]	4(-2) 2(-1) 3(1) / / 1(0)
7	Enqueue right child	5	0	{0:1,-1:2}	[(3,1),(4,-2),(5,0)]	4(-2) 2(-1) 3(1) / / 1(0) 5(0)
8	Dequeue node	3	1	{0:1,-1:2,1:3}	[(4,-2),(5,0)]	4(-2) 2(-1) 3(1) / / 1(0) 5(0)
9	Enqueue left child	6	0	{0:1,-1:2,1:3}	[(4,-2),(5,0),(6,0)]	4(-2) 2(-1) 3(1) / / 1(0) 5(0) 6(0)
10	Enqueue right child	7	2	{0:1,-1:2,1:3}	[(4,-2),(5,0),(6,0),(7,2)]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
11	Dequeue node	4	-2	{0:1,-1:2,1:3,-2:4}	[(5,0),(6,0),(7,2)]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
12	No children to enqueue	-	-	{0:1,-1:2,1:3,-2:4}	[(5,0),(6,0),(7,2)]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
13	Dequeue node	5	0	{0:1,-1:2,1:3,-2:4}	[(6,0),(7,2)]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
14	No children to enqueue	-	-	{0:1,-1:2,1:3,-2:4}	[(6,0),(7,2)]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
15	Dequeue node	6	0	{0:1,-1:2,1:3,-2:4}	[(7,2)]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
16	No children to enqueue	-	-	{0:1,-1:2,1:3,-2:4}	[(7,2)]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
17	Dequeue node	7	2	{0:1,-1:2,1:3,-2:4,2:7}	[]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
18	No children to enqueue	-	-	{0:1,-1:2,1:3,-2:4,2:7}	[]	4(-2) 2(-1) 3(1) 7(2) / / 1(0) 5(0) 6(0)
19	Queue empty, end traversal	-	-	{-2:4,-1:2,0:1,1:3,2:7}	[]	Top view nodes collected

💡 Queue is empty, all nodes processed

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 8	After Step 11	After Step 17	Final
Queue	[(1,0)]	[(2,-1),(3,1)]	[(3,1)]	[(4,-2),(5,0)]	[(5,0),(6,0),(7,2)]	[]	[]
Recorded hd nodes	{}	{0:1}	{0:1,-1:2}	{0:1,-1:2,1:3}	{0:1,-1:2,1:3,-2:4}	{-2:4,-1:2,0:1,1:3,2:7}	{-2:4,-1:2,0:1,1:3,2:7}

Key Moments - 3 Insights

Why do we only record the first node at each horizontal distance?

Because the top view shows the first node visible from the top at each horizontal distance. Later nodes at the same distance are hidden behind earlier ones. See execution_table rows 5, 8, and 11 where new hd keys are added only once.

Why do we use a queue and level order traversal instead of DFS?

Level order ensures we visit nodes top-down, so the first node at each horizontal distance is the topmost. DFS might visit lower nodes first, causing incorrect top view. The queue state in execution_table shows this order.

What does horizontal distance represent and how is it updated?

Horizontal distance (hd) measures left-right position relative to root (hd=0). Left child hd = parent hd - 1, right child hd = parent hd + 1. This is shown in execution_table column 'Horizontal Distance (hd)'.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, which horizontal distances have been recorded?

A {0:1}

B {-1:2}

C {0:1, -1:2}

D {}

💡 Hint

Check the 'Recorded hd nodes' column at Step 5 in execution_table

At which step does the node with horizontal distance 2 get recorded?

A Step 17

B Step 7

C Step 10

D Step 11

💡 Hint

Look for when hd=2 appears in 'Recorded hd nodes' column in execution_table

If the left child of node 2 was missing, how would the recorded hd nodes change after Step 11?

A hd 0 would be missing

B hd -2 would not be recorded

C hd 1 would be missing

D No change

💡 Hint

Check which node corresponds to hd -2 in execution_table and what happens if it is missing

Concept Snapshot

Top View of Binary Tree:
- Traverse tree level order with queue
- Track horizontal distance (hd): root=0, left=hd-1, right=hd+1
- Record first node at each hd
- After traversal, print nodes in hd order
- Shows nodes visible from top
- Uses map/dictionary to store hd nodes

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. We use a queue to traverse the tree level by level. For each node, we check if its horizontal distance is recorded. If not, we record it as the topmost node at that distance. We add left and right children with updated horizontal distances to the queue. We continue until the queue is empty. Finally, we print the recorded nodes in order of horizontal distance. This method ensures we see the top view nodes correctly.

Practice

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

easy

A. Nodes visible when the tree is viewed from the top

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

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

D. All leaf nodes of the tree

Solution

1. Step 1: Understand the meaning of top view

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

2. Step 2: Compare with other views

   Left or right views show nodes from side angles, and leaf nodes are only the bottom nodes, not the top view.

3. Final Answer:

   Nodes visible when the tree is viewed from the top -> Option A

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view shows nodes visible from above the tree [OK]

Common Mistakes:

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

2. Which data structure is commonly used to find the top view of a binary tree in C?

easy

A. Stack

B. Queue

C. Hash Map

D. Linked List

Solution

1. Step 1: Identify traversal method for top view

   Top view is found using level order traversal, which uses a queue to process nodes level by level.

2. Step 2: Understand role of queue

   Queue helps visit nodes in order from top to bottom and left to right, needed for correct top view.

3. Final Answer:

   Queue -> Option B

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level order traversal in top view [OK]

Common Mistakes:

• Using stack which is for depth-first traversal
• Confusing hash map as traversal structure
• Using linked list instead of queue

3. What is the output top view of the binary tree below?

        1
       / \
      2   3
       \   \
        4   5
         \   \
          6   7

medium

A. [1, 2, 3, 4, 5]

B. [2, 1, 4, 6, 7]

C. [2, 1, 3, 4, 7]

D. [2, 1, 3, 5, 7]

Solution

1. Step 1: Assign horizontal distances

   Assign horizontal distance (HD) from root: root(1) = 0, left child decreases HD by 1, right child increases HD by 1. So, 2 = -1, 3 = 1, 4 = 0, 5 = 2, 6 = 1, 7 = 3.

2. Step 2: Select topmost nodes at each HD

   At HD -1: 2; HD 0: 1 (4 is lower); HD 1: 3 (6 is lower); HD 2: 5; HD 3: 7.

3. Final Answer:

   [2, 1, 3, 5, 7] -> Option D

4. Quick Check:

   Top view nodes by HD = [2,1,3,5,7] [OK]

Hint: Use horizontal distance and pick top nodes [OK]

Common Mistakes:

• Choosing lower nodes instead of top nodes
• Ignoring horizontal distance concept
• Mixing order of nodes in output

4. Consider this C code snippet to print top view of a binary tree:

void topView(Node* root) {
    if (!root) return;
    map topNode;
    queue> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        Node* node = p.first;
        int hd = p.second;
        if (topNode.find(hd) == topNode.end())
            topNode[hd] = node->data;
        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    for (auto it : topNode)
        cout << it.second << " ";
}

What is the error in this code?

medium

A. Incorrect horizontal distance calculation

B. Not checking if root is NULL

C. Using C++ STL map and queue in C code

D. Missing return statement in void function

Solution

1. Step 1: Identify language mismatch

   The code uses C++ STL containers like map and queue, but the function is declared in C style which does not support these STL features.

2. Step 2: Check other code parts

   Root NULL check is present, horizontal distance is correctly updated, and void functions do not require return statements.

3. Final Answer:

   Using C++ STL map and queue in C code -> Option C

4. Quick Check:

   C code cannot use C++ STL containers [OK]

Hint: C code can't use C++ STL containers like map or queue [OK]

Common Mistakes:

• Ignoring language differences between C and C++
• Thinking void functions need return
• Assuming horizontal distance logic is wrong

5. You have a binary tree where multiple nodes share the same horizontal distance and level. How should you modify the top view algorithm to always show the leftmost node at that horizontal distance?

hard

A. Store the first node encountered at each horizontal distance during level order traversal

B. Store the last node encountered at each horizontal distance during level order traversal

C. Store nodes with maximum depth at each horizontal distance

D. Store nodes with minimum depth at each horizontal distance but prefer right child first

Solution

1. Step 1: Understand node selection in top view

   Top view shows the first node encountered at each horizontal distance during level order traversal, which naturally picks the leftmost node at that distance.

2. Step 2: Avoid overwriting nodes

   By storing only the first node at each horizontal distance and ignoring later nodes, the leftmost node is preserved.

3. Final Answer:

   Store the first node encountered at each horizontal distance during level order traversal -> Option A

4. Quick Check:

   First node at HD = leftmost node [OK]

Hint: Keep first node per horizontal distance in level order [OK]

Common Mistakes:

• Overwriting with last node instead of first
• Choosing nodes by max depth instead of min
• Preferring right child first breaks leftmost rule