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.