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.

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. Nodes visible when the tree is viewed from above

D. All leaf nodes of the tree

Solution

1. Step 1: Understand the top view concept

   The top view of a binary tree shows nodes visible from the top, ignoring nodes hidden behind others vertically.

2. Step 2: Compare with other views

   Left or right views show nodes from sides, and leaf nodes are only the bottom-most nodes, so they differ from top view.

3. Final Answer:

   Nodes visible when the tree is viewed from above -> Option C

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view shows nodes visible from above only [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 TypeScript data structure is best suited to store nodes with their horizontal distances while computing the top view of a binary tree?

easy

A. Map (key-value pairs)

B. Array

C. Set

D. Stack

Solution

1. Step 1: Identify the need for key-value storage

   We need to store nodes with their horizontal distances as keys and node values as values.

2. Step 2: Choose the appropriate data structure

   A Map allows storing keys (horizontal distances) with corresponding node values efficiently.

3. Final Answer:

   Map (key-value pairs) -> Option A

4. Quick Check:

   Use Map for horizontal distance to node mapping [OK]

Hint: Use Map to link horizontal distance and node [OK]

Common Mistakes:

• Using Array which is index-based, not key-based
• Using Set which stores unique values without keys
• Using Stack which is LIFO, not suitable here

3. Given the following TypeScript code snippet for top view, what will be the printed output?

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

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(4);
root.left.right.right = new Node(5);
root.left.right.right.right = new Node(6);

function topView(root: Node) {
  const map = new Map();
  const queue: Array<[Node, number]> = [[root, 0]];

  while (queue.length) {
    const [node, hd] = queue.shift()!;
    if (!map.has(hd)) {
      map.set(hd, node.data);
    }
    if (node.left) queue.push([node.left, hd - 1]);
    if (node.right) queue.push([node.right, hd + 1]);
  }

  const sortedKeys = Array.from(map.keys()).sort((a, b) => a - b);
  const result = sortedKeys.map(key => map.get(key));
  console.log(result);
}

topView(root);

medium

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

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

C. [2, 1, 3]

D. [2, 1, 3, 6]

Solution

1. Step 1: Assign horizontal distances and track first nodes

   Root(1) at hd=0, left(2) at hd=-1, right(3) at hd=1. Next nodes 4 at hd=0 (ignored, already 1), 5 at hd=1 (ignored, already 3), 6 at hd=2 (new).

2. Step 2: Collect nodes in order of horizontal distance

   Sorted keys: -1, 0, 1, 2 with values 2, 1, 3, 6 respectively.

3. Final Answer:

   [2, 1, 3, 6] -> Option D

4. Quick Check:

   Top view nodes = [2, 1, 3, 6] [OK]

Hint: First node at each horizontal distance is in top view [OK]

Common Mistakes:

• Including nodes hidden behind others at same horizontal distance
• Not sorting horizontal distances before output
• Adding all nodes instead of first at each horizontal distance

4. Identify the bug in the following TypeScript code for top view of a binary tree:

function topView(root: Node) {
  const map = new Map();
  const queue: Array<[Node, number]> = [[root, 0]];

  while (queue.length) {
    const [node, hd] = queue.pop()!;
    if (!map.has(hd)) {
      map.set(hd, node.data);
    }
    if (node.left) queue.push([node.left, hd - 1]);
    if (node.right) queue.push([node.right, hd + 1]);
  }

  const sortedKeys = Array.from(map.keys()).sort((a, b) => a - b);
  const result = sortedKeys.map(key => map.get(key));
  console.log(result);
}

medium

A. Using queue.pop() instead of queue.shift() causes wrong traversal order

B. Not checking if root is null before processing

C. Not sorting the keys before printing result

D. Using Map instead of Set for horizontal distances

Solution

1. Step 1: Analyze queue operation impact

   Using pop() removes from end, making traversal depth-first instead of breadth-first, breaking horizontal distance order.

2. Step 2: Correct traversal method

   Using shift() removes from front, ensuring level order traversal needed for correct top view.

3. Final Answer:

   Using queue.pop() instead of queue.shift() causes wrong traversal order -> Option A

4. Quick Check:

   Use shift() for BFS queue [OK]

Hint: Use shift() for BFS queue, not pop() [OK]

Common Mistakes:

• Using pop() causing DFS instead of BFS
• Ignoring null root check (less critical here)
• Not sorting keys before output (code does sort)

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 node with the smallest value at each horizontal distance?

hard

A. Store all nodes at each horizontal distance and pick the last inserted node

B. Update the map only if the new node's value is smaller than the existing one at that horizontal distance

C. Ignore horizontal distance and print nodes in level order

D. Use a stack instead of a queue for traversal

Solution

1. Step 1: Understand the problem with duplicates

   When nodes share horizontal distance and level, default top view picks first encountered node, not necessarily smallest value.

2. Step 2: Modify map update condition

   Update the map only if the new node's value is smaller than the stored value for that horizontal distance to ensure smallest value is shown.

3. Final Answer:

   Update the map only if the new node's value is smaller than the existing one at that horizontal distance -> Option B

4. Quick Check:

   Keep smallest node value per horizontal distance [OK]

Hint: Update map only if new node value is smaller [OK]

Common Mistakes:

• Ignoring value comparison, keeping first node only
• Using stack breaks level order needed
• Storing all nodes wastes memory and complicates logic