Top View of Binary Tree in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top View for a Simple Binary Tree

What is the printed top view of the binary tree after running the given code?

DSA Typescript

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

function topView(root: Node | null): number[] {
  if (!root) return [];
  const map = new Map<number, number>();
  const queue: Array<{node: Node; hd: number}> = [{node: root, hd: 0}];
  let minHd = 0, maxHd = 0;

  while (queue.length > 0) {
    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});
    minHd = Math.min(minHd, hd);
    maxHd = Math.max(maxHd, hd);
  }

  const result = [];
  for (let i = minHd; i <= maxHd; i++) {
    result.push(map.get(i)!);
  }
  return result;
}

// Tree structure:
//       1
//      / \
//     2   3
//      \   \
//       4   5
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));

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

B [2, 1, 3]

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

D [2, 1, 3, 5]

💡 Hint

Think about horizontal distances from the root and which nodes appear first at each horizontal distance.

The top view shows the nodes visible when the tree is viewed from above. We track horizontal distances (hd) from the root (hd=0). For each hd, the first node encountered in level order traversal is included.

Here, nodes at hd -1 is 2, hd 0 is 1, hd 1 is 3, and hd 2 is 5. Node 4 is at hd 0 but appears after 1, so it is not included.

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Top View

In the top view of a binary tree, what does the 'horizontal distance' (hd) represent?

A The relative horizontal position of a node from the root, where left child decreases hd by 1 and right child increases hd by 1.

B The distance of a node from the root measured along the edges.

C The depth of a node in the tree, counting edges from the root.

D The vertical level of a node from the root, starting at 0 for the root.

💡 Hint

Think about how left and right children affect the horizontal position relative to the root.

Horizontal distance is a measure of how far left or right a node is from the root node. The root has hd = 0. Moving left decreases hd by 1, moving right increases hd by 1.

🔧 Debug

advanced

Identify the Bug in Top View Implementation

What error will this code produce when run, and why? function topView(root) { if (!root) return []; const map = new Map(); const queue = [{node: root, hd: 0}]; while (queue.length > 0) { 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 Array.from(map.values()); }

A Returns the correct top view array.

B Throws a TypeError because map is used incorrectly.

C Returns an empty array because queue.pop() removes from the end, causing incorrect traversal order.

D Returns a reversed top view array compared to expected output.

💡 Hint

Consider how queue.pop() affects the order of node processing compared to queue.shift().

The code uses queue.pop() which removes the last element, making the traversal depth-first instead of breadth-first. This causes nodes to be processed in the wrong order, so the first node at each horizontal distance may be missed, resulting in an incomplete or empty map.

🚀 Application

advanced

Top View of a Complex Binary Tree

Given the binary tree below, what is the top view output? // Tree structure: // 10 // / \ // 5 15 // / \ \ // 3 7 18 // \ / // 4 16 Use the top view logic where the first node at each horizontal distance is included.

A [3, 5, 10, 15, 16, 18]

B [3, 5, 10, 15, 18]

C [4, 5, 10, 15, 18]

D [3, 4, 5, 10, 15, 18]

💡 Hint

Calculate horizontal distances for each node and pick the first node encountered at each hd in level order.

Horizontal distances: 10 (0), 5 (-1), 15 (1), 3 (-2), 7 (0), 18 (2), 4 (-1), 16 (1).

First nodes at each hd: -2:3, -1:5, 0:10, 1:15, 2:18.

Nodes 4, 7, 16 are not first at their hd.

🧠 Conceptual

expert

Why Use Breadth-First Search for Top View?

Why is breadth-first search (BFS) preferred over depth-first search (DFS) when computing the top view of a binary tree?

A BFS processes nodes level by level, ensuring the first node at each horizontal distance is recorded, while DFS may miss this order.

B DFS uses less memory, so it is not suitable for top view calculation.

C BFS visits nodes in random order, which helps find the top view faster.

D DFS cannot track horizontal distances, so it cannot be used for top view.

💡 Hint

Think about the order nodes are visited and how that affects which nodes appear in the top view.

BFS visits nodes level by level, so the first node encountered at each horizontal distance is guaranteed to be the topmost node. DFS may visit deeper nodes first, missing the correct top view nodes.