Top View of Binary Tree in DSA Typescript

Mental Model

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

Analogy: Imagine standing on a balcony looking down at a garden with trees; you only see the tops of some trees because others block your view behind them.

      1
     / \
    2   3
     \   \
      4   5

Top view shows nodes: 2 -> 1 -> 3 -> 5

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 \ \ 4 5 Find top view nodes

Goal: Identify nodes visible from the top, ordered from leftmost to rightmost horizontal position

Step 1: Start at root node 1 with horizontal distance (hd) = 0

Queue: [(1, hd=0)]
Top view map: {}

Why: Root is the starting point and has horizontal distance zero

Step 2: Dequeue node 1, record hd=0 in top view map as 1

Queue: []
Top view map: {0: 1}

Why: First node at hd=0 is visible from top

Step 3: Enqueue left child 2 with hd=-1 and right child 3 with hd=1

Queue: [(2, hd=-1), (3, hd=1)]
Top view map: {0: 1}

Why: Left child is one step left, right child one step right

Step 4: Dequeue node 2, record hd=-1 in top view map as 2

Queue: [(3, hd=1)]
Top view map: {-1: 2, 0: 1}

Why: First node at hd=-1 is visible from top

Step 5: Enqueue right child 4 of node 2 with hd=0

Queue: [(3, hd=1), (4, hd=0)]
Top view map: {-1: 2, 0: 1}

Why: Child 4 is at hd=0 but hd=0 already recorded, so ignore for top view

Step 6: Dequeue node 3, record hd=1 in top view map as 3

Queue: [(4, hd=0)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: First node at hd=1 is visible from top

Step 7: Enqueue right child 5 of node 3 with hd=2

Queue: [(4, hd=0), (5, hd=2)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: Child 5 is at hd=2, not recorded yet

Step 8: Dequeue node 4 at hd=0, hd=0 already recorded, ignore

Queue: [(5, hd=2)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: Only first node at each hd is visible from top

Step 9: Dequeue node 5, record hd=2 in top view map as 5

Queue: []
Top view map: {-1: 2, 0: 1, 1: 3, 2: 5}

Why: First node at hd=2 is visible from top

Result:

Top view nodes in order of hd: 2 -> 1 -> 3 -> 5

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function topView(root: TreeNode | null): number[] {
  if (!root) return [];

  // Map to store first node at each horizontal distance
  const topViewMap = new Map<number, number>();
  // Queue holds pairs of node and its horizontal distance
  const queue: Array<[TreeNode, number]> = [];
  queue.push([root, 0]);

  while (queue.length > 0) {
    const [node, hd] = queue.shift()!;

    // Record the node value if hd not seen before
    if (!topViewMap.has(hd)) {
      topViewMap.set(hd, node.val);
    }

    // Enqueue left child with hd - 1
    if (node.left) {
      queue.push([node.left, hd - 1]);
    }

    // Enqueue right child with hd + 1
    if (node.right) {
      queue.push([node.right, hd + 1]);
    }
  }

  // Extract entries sorted by horizontal distance
  const sortedKeys = Array.from(topViewMap.keys()).sort((a, b) => a - b);
  return sortedKeys.map(key => topViewMap.get(key)!);
}

// Driver code to test
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(5);

const result = topView(root);
console.log(result.join(' -> '));

queue.push([root, 0]);

Initialize queue with root node at horizontal distance 0

const [node, hd] = queue.shift()!;

Dequeue node and its horizontal distance for processing

if (!topViewMap.has(hd)) { topViewMap.set(hd, node.val); }

Record first node encountered at this horizontal distance

if (node.left) { queue.push([node.left, hd - 1]); }

Add left child with horizontal distance one less

if (node.right) { queue.push([node.right, hd + 1]); }

Add right child with horizontal distance one more

const sortedKeys = Array.from(topViewMap.keys()).sort((a, b) => a - b);

Sort horizontal distances to output top view left to right

return sortedKeys.map(key => topViewMap.get(key)!);

Return node values in top view order

Output

2 -> 1 -> 3 -> 5

Complexity Analysis

Time: O(n) because each node is visited once during BFS traversal

Space: O(n) for the queue and map storing nodes and horizontal distances

vs Alternative: Naive approach might try vertical traversal multiple times causing more than O(n) time; BFS with map is efficient

Edge Cases

Empty tree (root is null)

Returns empty list as there are no nodes to view

DSA Typescript

if (!root) return [];

Tree with only root node

Returns list with single root node value

DSA Typescript

queue.push([root, 0]);

Tree with multiple nodes at same horizontal distance

Only the first node encountered at that horizontal distance is recorded for top view

DSA Typescript

if (!topViewMap.has(hd)) { topViewMap.set(hd, node.val); }

When to Use This Pattern

When asked to find nodes visible from top or side in a tree, use BFS with horizontal distance tracking to capture first nodes at each position.

Common Mistakes

Mistake: Recording all nodes at a horizontal distance instead of only the first one
Fix: Check if horizontal distance is already recorded before adding a node to top view map

Mistake: Using DFS which can miss the correct order of nodes for top view
Fix: Use BFS to process nodes level by level ensuring first nodes at each horizontal distance are captured

Summary

Shows nodes visible when looking down on a binary tree from above.

Use when you need to find the topmost nodes at each horizontal position in a tree.

Track horizontal distances with BFS and record only the first node at each distance.

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