Top View of Binary Tree in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a binary tree node class with left and right children.

DSA Typescript

class Node {
  value: number;
  left: Node | null;
  right: Node | null;
  constructor(value: number) {
    this.value = value;
    this.left = [1];
    this.right = null;
  }
}

Drag options to blanks, or click blank then click option'

A0

Bundefined

Cnull

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or false instead of null for child nodes.

Leaving the child uninitialized.

In TypeScript, to indicate no child node, we use null to initialize left and right pointers.

2fill in blank

medium

Complete the code to insert a node into the binary tree at the left child.

DSA Typescript

function insertLeft(parent: Node, value: number): void {
  parent.left = new Node([1]);
}

Drag options to blanks, or click blank then click option'

Avalue

Bparent.value

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Using parent.value instead of the new value.

Assigning null or undefined instead of a new node.

We create a new node with the given value to insert as the left child.

3fill in blank

hard

Fix the error in the function to compute the top view by completing the missing code to track horizontal distance.

DSA Typescript

function topView(root: Node): number[] {
  if (!root) return [];
  const queue: Array<[Node, number]> = [[root, 0]];
  const map = new Map<number, number>();
  while (queue.length > 0) {
    const [node, hd] = queue.shift()!;
    if (!map.has([1])) {
      map.set(hd, node.value);
    }
    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)!);
  return result;
}

Drag options to blanks, or click blank then click option'

Aqueue.length

Bhd

Cnode.value

Dnode.left

Attempts:

3 left

💡 Hint

Common Mistakes

Checking node.value instead of hd in the map.

Using queue length or node.left as key mistakenly.

We check if the horizontal distance 'hd' is already in the map to decide if we add the node's value.

4fill in blank

hard

Fill both blanks to correctly update the queue with child nodes and their horizontal distances.

DSA Typescript

if (node.left) queue.push([node.left, [1]]);
if (node.right) queue.push([node.right, [2]]);

Drag options to blanks, or click blank then click option'

Ahd - 1

Bhd + 1

Chd

Dnode.value

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same horizontal distance for both children.

Using node.value instead of hd adjustments.

Left child is at horizontal distance one less than parent, right child is one more.

5fill in blank

hard

Fill all three blanks to return the top view values sorted by horizontal distance.

DSA Typescript

const sortedKeys = Array.from(map.keys()).sort((a, b) => [1]);
const result = sortedKeys.map(key => map.get([2])!);
return [3];

Drag options to blanks, or click blank then click option'

Aa - b

Bkey

Cresult

Db - a

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting keys descending (b - a) instead of ascending.

Returning keys instead of mapped values.

Using wrong variable names.

Sort keys ascending (a - b), map keys to values, then return the result array.

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