Top View of Binary Tree in DSA Javascript

Mental Model

We want to see the nodes visible when looking at the tree 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 branches, not the ones hidden behind taller branches.

       1
      / \
     2   3
      \   \
       4   5

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

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 \ \ 4 5

Goal: Print nodes visible from the top view: nodes that appear first at each horizontal distance from root.

Step 1: Start BFS from root (1) at horizontal distance (hd) 0

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

Why: We begin from the root to explore all nodes level by level with their horizontal distances

Step 2: Dequeue (1, hd=0), add 1 to top view map at hd=0

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

Why: First node at hd=0 is 1, so it is visible from top

Step 3: Enqueue left child (2, hd=-1) and right child (3, hd=1)

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

Why: Children are added with updated horizontal distances

Step 4: Dequeue (2, hd=-1), add 2 to top view map at hd=-1

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

Why: First node at hd=-1 is 2, so it is visible from top

Step 5: Enqueue right child (4, hd=0) of node 2

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

Why: 4 is at hd=0 but 1 is already recorded, so 4 won't overwrite

Step 6: Dequeue (3, hd=1), add 3 to top view map at hd=1

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

Why: First node at hd=1 is 3, so it is visible from top

Step 7: Enqueue right child (5, hd=2) of node 3

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

Why: 5 is added with hd=2

Step 8: Dequeue (4, hd=0), hd=0 already has 1, so skip adding 4

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 (5, hd=2), add 5 to top view map at hd=2

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

Why: First node at hd=2 is 5, so it is visible from top

Result:

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

Annotated Code

DSA Javascript

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

function topView(root) {
  if (!root) return;
  const queue = [];
  const topViewMap = new Map();
  queue.push({ node: root, hd: 0 });

  while (queue.length > 0) {
    const { node, hd } = queue.shift();
    if (!topViewMap.has(hd)) {
      topViewMap.set(hd, node.data);
    }
    if (node.left) {
      queue.push({ node: node.left, hd: hd - 1 });
    }
    if (node.right) {
      queue.push({ node: node.right, hd: hd + 1 });
    }
  }

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

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

topView(root);

queue.push({ node: root, hd: 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.data); }

Record first node encountered at this horizontal distance

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

Add left child with horizontal distance decreased by 1

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

Add right child with horizontal distance increased by 1

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

Sort horizontal distances to print top view from left to right

console.log(result.join(' -> '));

Print the top view nodes in 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 their horizontal distances

vs Alternative: Naive approach might try to print top view by multiple traversals causing O(n^2) time; BFS with map is efficient

Edge Cases

Empty tree (root is null)

Function returns without printing anything

DSA Javascript

if (!root) return;

Tree with only root node

Prints the root node as the top view

DSA Javascript

queue.push({ node: root, hd: 0 });

Multiple nodes at same horizontal distance

Only the first node encountered at that horizontal distance is printed

DSA Javascript

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

When to Use This Pattern

When asked to print nodes visible from the top of a binary tree, use BFS with horizontal distances to track first nodes at each horizontal level.

Common Mistakes

Mistake: Overwriting nodes in the map for the same horizontal distance instead of keeping the first one
Fix: Check if horizontal distance is already in map before adding a node

Mistake: Using DFS which can miss nodes visible from top due to traversal order
Fix: Use BFS to ensure level order traversal and correct top view

Summary

Prints the nodes visible when looking at a binary tree from above.

Use when you need to find the top view of a binary tree in level order.

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