Top View of Binary Tree in DSA Javascript - 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 for top view

↓

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 Javascript

function topView(root) {
  let queue = [{node: root, hd: 0}];
  let topViewMap = new Map();
  while(queue.length) {
    let {node, hd} = queue.shift();
    if (!topViewMap.has(hd)) topViewMap.set(hd, node.val);
    if (node.left) queue.push({node: node.left, hd: hd - 1});
    if (node.right) queue.push({node: node.right, hd: hd + 1});
  }
  return [...topViewMap.entries()].sort((a,b) => a[0]-b[0]).map(x => x[1]);
}

This code finds the top view of a binary tree by level order traversal and tracking horizontal distances.

Execution Table

Step	Operation	Node Visited (val)	Horizontal Distance (hd)	Top View Map (hd: val)	Queue State	Visual State
1	Start with root	1	0	{}	[{node:1, hd:0}]	1(0)
2	Dequeue node	1	0	{0:1}	[{node:2, hd:-1}, {node:3, hd:1}]	1(0)
3	Dequeue node	2	-1	{0:1, -1:2}	[{node:3, hd:1}, {node:4, hd:-2}, {node:5, hd:0}]	2(-1) -> 1(0)
4	Dequeue node	3	1	{0:1, -1:2, 1:3}	[{node:4, hd:-2}, {node:5, hd:0}, {node:6, hd:0}, {node:7, hd:2}]	2(-1) -> 1(0) -> 3(1)
5	Dequeue node	4	-2	{0:1, -1:2, 1:3, -2:4}	[{node:5, hd:0}, {node:6, hd:0}, {node:7, hd:2}]	4(-2) -> 2(-1) -> 1(0) -> 3(1)
6	Dequeue node	5	0	{0:1, -1:2, 1:3, -2:4}	[{node:6, hd:0}, {node:7, hd:2}]	4(-2) -> 2(-1) -> 1(0) -> 3(1)
7	Dequeue node	6	0	{0:1, -1:2, 1:3, -2:4}	[{node:7, hd:2}]	4(-2) -> 2(-1) -> 1(0) -> 3(1)
8	Dequeue node	7	2	{0:1, -1:2, 1:3, -2:4, 2:7}	[]	4(-2) -> 2(-1) -> 1(0) -> 3(1) -> 7(2)
9	Queue empty	-	-	{-2:4, -1:2, 0:1, 1:3, 2:7}	[]	Top view nodes collected

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

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}]	[]	[]
topViewMap	{}	{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 steps 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 depth-first traversal?

Level order ensures we visit nodes top-down, so the first node at each horizontal distance is the topmost. Depth-first might visit lower nodes first, causing incorrect top view. See execution_table steps showing queue states.

How do horizontal distances change when moving left or right?

Moving left decreases horizontal distance by 1, moving right increases it by 1. This helps track node positions horizontally. See execution_table steps 3 and 4 where left child hd is hd-1 and right child hd is hd+1.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what nodes are currently in the topViewMap?

A {0:1, -1:2, 1:3, -2:4}

B {0:1, -1:2, 1:3}

C {-1:2, 1:3, -2:4}

D {}

💡 Hint

Check the 'Top View Map' column at Step 5 in execution_table

At which step does the horizontal distance 2 first get added to the topViewMap?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look for when hd=2 appears in the 'Top View Map' column in execution_table

If the root node had no left child, how would the queue state change after Step 2?

A Queue would have only right child with hd=1

B Queue would be empty

C Queue would have left child with hd=-1

D Queue would have both children with hd=0

💡 Hint

Refer to queue state changes in variable_tracker and execution_table Step 2

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 = parent hd - 1
- Right child hd = parent hd + 1
- Sort map by hd keys to print top view

Full Transcript

To find the top view of a binary tree, we start at the root with horizontal distance zero. We use a queue to do a level order traversal. For each node, if its horizontal distance is not recorded yet, we add it to the top view map. We enqueue left and right children with hd-1 and hd+1 respectively. This way, the first node encountered at each horizontal distance is recorded. After processing all nodes, we sort the map by horizontal distance and print the node values. This method ensures we see the nodes visible from the top, ignoring nodes hidden behind others at the same horizontal distance.