Top View of Binary Tree in DSA Typescript - 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?

↓

Add node to top view

↓

Ignore node

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Sort nodes by horizontal distance

↓

Print top view nodes

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

Execution Sample

DSA Typescript

class Node {
  constructor(public val: number, public left: Node | null = null, public right: Node | null = null) {}
}

function topView(root: Node): number[] {
  // Implementation
}

This code defines a binary tree node and a function to find the top view of the tree.

Execution Table

Step	Operation	Node Visited (Value)	Horizontal Distance (hd)	Top View Map (hd -> node)	Queue State	Visual State
1	Start at root	1	0	{}	[ (1, hd=0) ]	[]
2	Dequeue node	1	0	{0:1}	[ (2, hd=-1), (3, hd=1) ]	[hd=0:1]
3	Dequeue node	2	-1	{0:1, -1:2}	[ (3, hd=1), (4, hd=-2), (5, hd=0) ]	[hd=-1:2, hd=0:1]
4	Dequeue node	3	1	{0:1, -1:2, 1:3}	[ (4, hd=-2), (5, hd=0), (6, hd=0), (7, hd=2) ]	[hd=-1:2, hd=0:1, hd=1:3]
5	Dequeue node	4	-2	{0:1, -1:2, 1:3, -2:4}	[ (5, hd=0), (6, hd=0), (7, hd=2) ]	[hd=-2:4, hd=-1:2, hd=0:1, hd=1:3]
6	Dequeue node	5	0	{0:1, -1:2, 1:3, -2:4}	[ (6, hd=0), (7, hd=2) ]	[hd=-2:4, hd=-1:2, hd=0:1, hd=1:3]
7	Dequeue node	6	0	{0:1, -1:2, 1:3, -2:4}	[ (7, hd=2) ]	[hd=-2:4, hd=-1:2, hd=0:1, hd=1:3]
8	Dequeue node	7	2	{0:1, -1:2, 1:3, -2:4, 2:7}	[]	[hd=-2:4, hd=-1:2, hd=0:1, hd=1:3, hd=2:7]
9	Queue empty	N/A	N/A	Final top view map	[]	[hd=-2:4, hd=-1:2, hd=0:1, hd=1:3, hd=2:7]

💡 Queue is empty, all nodes processed.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
Queue	[(1,0)]	[(2,-1),(3,1)]	[(3,1),(4,-2),(5,0)]	[(4,-2),(5,0),(6,0),(7,2)]	[(5,0),(6,0),(7,2)]	[(6,0),(7,2)]	[(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}	{0:1,-1:2,1:3,-2:4}	{0:1,-1:2,1:3,-2:4,2:7}	{-2:4,-1:2,0:1,1:3,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 rows 2, 3, and 6 where nodes with hd=0 are ignored after the first.

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 state changes in execution_table.

How do horizontal distances change when moving left or right?

Moving left decreases horizontal distance by 1, moving right increases it by 1. This is tracked in the queue state and horizontal distance column in execution_table steps 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which nodes are currently in the queue?

A [(6, hd=0), (7, hd=2)]

B [(4, hd=-2), (5, hd=0), (6, hd=0), (7, hd=2)]

C [(5, hd=0), (6, hd=0), (7, hd=2)]

D [(7, hd=2)]

💡 Hint

Check the 'Queue State' column in execution_table row 5.

At which step does the top view map first include a node with horizontal distance 1?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Top View Map' column in execution_table rows 2 to 5.

If the node with value 3 had no right child, how would the final top view map change?

A It would include an extra node at hd=2.

B It would not include horizontal distance 2.

C It would include node 3 twice.

D It would be empty.

💡 Hint

Check execution_table step 8 where hd=2 is added by node 7, a right child of 3.

Concept Snapshot

Top View of Binary Tree:
- Use level order traversal with a queue.
- Track horizontal distance (hd) for each node.
- For left child, hd = parent hd - 1.
- For right child, hd = parent hd + 1.
- Record first node at each hd in a map.
- Sort map keys and print nodes 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. For each node, we check if its horizontal distance is already recorded in the top view map. If not, we add it. We enqueue left and right children with horizontal distances decreased or increased by one, respectively. We continue until the queue is empty. Finally, we sort the recorded nodes by horizontal distance and print them. This ensures we see the topmost nodes visible from above.