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.

Practice

1. What does the top view of a binary tree represent?

easy

A. All leaf nodes of the tree

B. Nodes visible when the tree is viewed from the left side

C. Nodes visible when the tree is viewed from the right side

D. Nodes visible when the tree is viewed from above

Solution

1. Step 1: Understand the top view concept

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

2. Step 2: Compare with other views

   Left or right views show nodes from sides, and leaf nodes are only the bottom nodes.

3. Final Answer:

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

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 JavaScript data structure is best suited to store nodes by their horizontal distance when computing the top view of a binary tree?

easy

A. Set

B. Array

C. Map

D. Stack

Solution

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

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

2. Step 2: Choose the best data structure

   A Map allows storing key-value pairs with efficient lookup and insertion.

3. Final Answer:

   Map -> Option C

4. Quick Check:

   Map stores horizontal distance keys [OK]

Hint: Use Map for key-value horizontal distance storage [OK]

Common Mistakes:

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

3. What is the output of the following code snippet that prints the top view of the binary tree?

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

function topView(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [{ node: root, hd: 0 }];
  while (queue.length) {
    const { node, hd } = queue.shift();
    if (!map.has(hd)) map.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 });
  }
  return [...map.entries()]
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

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);

console.log(topView(root));

medium

A. [2, 1, 3, 5]

B. [2, 1, 3]

C. [2, 1, 4, 3, 5]

D. [1, 2, 3, 4, 5]

Solution

1. Step 1: Traverse the tree with horizontal distances

   Start at root (1) with hd=0, add left child (2) hd=-1, right child (3) hd=1, then 4 at hd=0 (ignored since hd=0 exists), 5 at hd=2.

2. Step 2: Collect first nodes at each horizontal distance

   Map stores hd:-1=2, hd:0=1, hd:1=3, hd:2=5. Sorted by hd: -1,0,1,2 gives [2,1,3,5].

3. Final Answer:

   [2, 1, 3, 5] -> Option A

4. Quick Check:

   Top view nodes by hd = [2,1,3,5] [OK]

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

Common Mistakes:

• Including nodes hidden behind others at same hd
• Not sorting by horizontal distance before output
• Adding nodes multiple times for same hd

4. Identify the bug in this top view function and select the correct fix:

function topView(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [{ node: root, hd: 0 }];
  while (queue.length) {
    const { node, hd } = queue.pop();
    if (!map.has(hd)) map.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 });
  }
  return [...map.entries()]
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

medium

A. Replace queue.pop() with queue.shift() to process nodes in correct order

B. Change map to a Set to avoid duplicate nodes

C. Remove sorting before returning the result

D. Add a visited set to avoid infinite loops

Solution

1. Step 1: Understand queue usage in BFS

   Using queue.pop() removes last element, making it a stack (DFS), not BFS. BFS requires queue.shift() to process nodes in FIFO order.

2. Step 2: Fix the traversal order

   Replacing pop() with shift() ensures nodes are processed level by level, correctly capturing top view nodes.

3. Final Answer:

   Replace queue.pop() with queue.shift() to process nodes in correct order -> Option A

4. Quick Check:

   BFS needs shift(), not pop() [OK]

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

Common Mistakes:

• Using pop() causing wrong traversal order
• Using Set instead of Map losing key-value pairs
• Skipping sorting which orders output incorrectly

5. Given a binary tree where multiple nodes share the same horizontal distance and level, how should the top view algorithm decide which node to include in the output?

hard

A. Include the node that appears last in level order traversal at that horizontal distance

B. Include the node that appears first in level order traversal at that horizontal distance

C. Include the node with the maximum value at that horizontal distance

D. Include all nodes at that horizontal distance

Solution

1. Step 1: Understand node conflicts at same horizontal distance and level

   When nodes share horizontal distance and level, top view includes the first encountered node in level order (BFS) traversal.

2. Step 2: Reason why first node is chosen

   Because BFS visits nodes level by level from left to right, the first node at that horizontal distance is visible from top.

3. Final Answer:

   Include the node that appears first in level order traversal at that horizontal distance -> Option B

4. Quick Check:

   Top view = first node at hd in BFS order [OK]

Hint: Pick first node at horizontal distance in BFS [OK]

Common Mistakes:

• Choosing node by max value instead of order
• Including all nodes causing duplicates
• Choosing last node instead of first