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

↓

Pop node from queue

↓

Check if horizontal distance seen before?

↓

Print/store node

↓

Add left child with hd-1 to queue

↓

Add right child with hd+1 to queue

↓

Repeat until queue empty

↓

Output collected nodes in order of horizontal distance

Traverse the tree level by level, track horizontal distances, and print the first node seen at each horizontal distance to get the top view.

Execution Sample

DSA C++

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

void topView(Node* root) {
  // Implementation
}

This code prints the top view of a binary tree by level order traversal with horizontal distance tracking.

Execution Table

Step	Operation	Node Visited (data)	Horizontal Distance (hd)	Queue State (node:hd)	Top View Map (hd:data)	Visual State
1	Start at root	1	0	[ (1:0) ]	{}	Tree: 1 Queue: 1:0 TopView: {}
2	Pop node	1	0	[]	{0:1}	Tree: 1 Queue: empty TopView: 0->1
3	Add left child	2	-1	[ (2:-1) ]	{0:1}	Tree: 1 Queue: 2:-1 TopView: 0->1
4	Add right child	3	1	[ (2:-1), (3:1) ]	{0:1}	Tree: 1 Queue: 2:-1,3:1 TopView: 0->1
5	Pop node	2	-1	[ (3:1) ]	{0:1, -1:2}	Tree: 1 Queue: 3:1 TopView: -1->2,0->1
6	Add left child	4	-2	[ (3:1), (4:-2) ]	{0:1, -1:2}	Tree: 1 Queue: 3:1,4:-2 TopView: -1->2,0->1
7	Add right child	5	0	[ (3:1), (4:-2), (5:0) ]	{0:1, -1:2}	Tree: 1 Queue: 3:1,4:-2,5:0 TopView: -1->2,0->1
8	Pop node	3	1	[ (4:-2), (5:0) ]	{0:1, -1:2, 1:3}	Tree: 1 Queue: 4:-2,5:0 TopView: -1->2,0->1,1->3
9	Add left child	6	0	[ (4:-2), (5:0), (6:0) ]	{0:1, -1:2, 1:3}	Tree: 1 Queue: 4:-2,5:0,6:0 TopView: -1->2,0->1,1->3
10	Add right child	7	2	[ (4:-2), (5:0), (6:0), (7:2) ]	{0:1, -1:2, 1:3}	Tree: 1 Queue: 4:-2,5:0,6:0,7:2 TopView: -1->2,0->1,1->3
11	Pop node	4	-2	[ (5:0), (6:0), (7:2) ]	{0:1, -1:2, 1:3, -2:4}	Tree: 1 Queue: 5:0,6:0,7:2 TopView: -2->4,-1->2,0->1,1->3
12	No children to add	-	-	[ (5:0), (6:0), (7:2) ]	{0:1, -1:2, 1:3, -2:4}	Tree: 1 Queue: 5:0,6:0,7:2 TopView: -2->4,-1->2,0->1,1->3
13	Pop node	5	0	[ (6:0), (7:2) ]	{0:1, -1:2, 1:3, -2:4}	Tree: 1 Queue: 6:0,7:2 TopView: -2->4,-1->2,0->1,1->3
14	No children to add	-	-	[ (6:0), (7:2) ]	{0:1, -1:2, 1:3, -2:4}	Tree: 1 Queue: 6:0,7:2 TopView: -2->4,-1->2,0->1,1->3
15	Pop node	6	0	[ (7:2) ]	{0:1, -1:2, 1:3, -2:4}	Tree: 1 Queue: 7:2 TopView: -2->4,-1->2,0->1,1->3
16	No children to add	-	-	[ (7:2) ]	{0:1, -1:2, 1:3, -2:4}	Tree: 1 Queue: 7:2 TopView: -2->4,-1->2,0->1,1->3
17	Pop node	7	2	[]	{0:1, -1:2, 1:3, -2:4, 2:7}	Tree: 1 Queue: empty TopView: -2->4,-1->2,0->1,1->3,2->7
18	No children to add	-	-	[]	{0:1, -1:2, 1:3, -2:4, 2:7}	Tree: 1 Queue: empty TopView: -2->4,-1->2,0->1,1->3,2->7
19	Queue empty	-	-	[]	{0:1, -1:2, 1:3, -2:4, 2:7}	Traversal complete, top view collected

💡 Queue is empty, all nodes processed

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	After Step 17	Final
Queue	[ (1:0) ]	[]	[ (3:1) ]	[ (4:-2), (5:0) ]	[ (5:0), (6:0), (7:2) ]	[]	[]
Top View Map	{}	{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:7}	{0:1, -1:2, 1:3, -2:4, 2:7}

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 the first one. See execution_table steps 2, 5, and 8 where nodes are added only if hd is new.

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

Level order traversal 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. This is shown in the queue states in execution_table.

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

Horizontal distance (hd) is the relative position from root: root is 0, left child is hd-1, right child is hd+1. This helps group nodes vertically. See execution_table steps 3, 4, 6, 7 for hd updates.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the top view map after visiting node 2?

A {0:1, -1:2}

B {0:1}

C {-1:2}

D {}

💡 Hint

Check the 'Top View Map' column at step 5 in execution_table.

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

A Step 11

B Step 17

C Step 8

D Step 2

💡 Hint

Look for when hd=2 is added to 'Top View Map' in execution_table.

If the node with data 5 had a left child, how would the queue state change after step 14?

A A new node with hd= -1 would be added to the queue

B A new node with hd= 1 would be added to the queue

C A new node with hd= 0 would be added to the queue

D No change to the queue

💡 Hint

Children's hd is parent's hd ± 1; node 5 has hd=0, so left child hd=0-1= -1, right child hd=0+1=1.

Concept Snapshot

Top View of Binary Tree:
- Use level order traversal with a queue
- Track horizontal distance (hd) for each node
- For each hd, store first node encountered
- Left child hd = parent hd - 1
- Right child hd = parent hd + 1
- Output nodes sorted by hd for top view

Full Transcript

To find the top view of a binary tree, we start at the root node with horizontal distance zero. We use a queue to do a level order traversal, visiting nodes level by level. For each node, we check if its horizontal distance has been seen before. If not, we add it to the top view map. We add left and right children to the queue with horizontal distances decreased or increased by one respectively. We continue until the queue is empty. The top view is the collection of first nodes seen at each horizontal distance, printed from leftmost to rightmost. This method ensures we see the topmost nodes when looking from above the tree.