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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom View for a Simple Binary Tree

What is the bottom view of the following binary tree after running the given TypeScript code?

DSA Typescript

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

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

  while (queue.length > 0) {
    const {node, hd} = queue.shift()!;
    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.entries())
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

// Tree construction
const root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

console.log(bottomView(root));

A [8, 10, 3, 14, 25]

B [5, 10, 3, 14, 25]

C [5, 8, 3, 14, 22]

D [5, 8, 10, 14, 25]

💡 Hint

Remember bottom view shows the last node at each horizontal distance when viewed from bottom.

The bottom view includes nodes visible when the tree is viewed from the bottom. The horizontal distances (hd) are used to track nodes. The last node encountered at each hd is stored.

For this tree, the bottom view nodes by hd are: hd=-2:5, hd=-1:10, hd=0:3, hd=1:14, hd=2:25.

🧠 Conceptual

intermediate

Horizontal Distance in Bottom View

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

A The depth of a node in the tree

B The vertical level of a node from the root

C The distance of a node from the root along the horizontal axis, with root at 0, left child hd-1, right child hd+1

D The number of nodes in the subtree rooted at that node

💡 Hint

Think about how nodes are positioned left or right 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, left child decreases hd by 1, right child increases hd by 1.

🔧 Debug

advanced

Identify the Error in Bottom View Implementation

What error will occur when running this TypeScript code for bottom view of a binary tree?

DSA Typescript

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

  while (queue.length > 0) {
    const {node, hd} = queue.pop()!;
    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.entries())
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

A The code throws a SyntaxError due to missing semicolons

B The code throws a TypeError because queue.pop() returns undefined

C The code runs correctly and returns the bottom view

D The code returns an incorrect bottom view because it uses pop() instead of shift() causing wrong traversal order

💡 Hint

Consider how pop() and shift() affect the order of nodes processed in a queue.

Using pop() makes the queue behave like a stack (LIFO), which changes the traversal order from level order to depth-first. This causes the bottom view to be incorrect.

🚀 Application

advanced

Bottom View with Duplicate Horizontal Distances

Given the binary tree below, what is the bottom view output? Tree structure: - Root: 1 - Root.left: 2 - Root.right: 3 - Root.left.right: 4 - Root.right.left: 5 - Root.right.right: 6 - Root.right.left.left: 7 - Root.right.left.right: 8

DSA Typescript

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

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

  while (queue.length > 0) {
    const {node, hd} = queue.shift()!;
    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.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.left = new Node(5);
root.right.right = new Node(6);
root.right.left.left = new Node(7);
root.right.left.right = new Node(8);

console.log(bottomView(root));

A [7, 5, 8, 6]

B [2, 4, 7, 5, 6]

C [2, 4, 5, 8, 6]

D [2, 4, 7, 8, 6]

💡 Hint

Remember bottom view shows the last node at each horizontal distance after level order traversal.

Horizontal distances and last nodes at each hd: hd=-1:7 (2 overwritten by 7), hd=0:5 (1 overwritten by 4 then 5), hd=1:8 (3 overwritten by 8), hd=2:6.

Sorted by hd ascending: [7, 5, 8, 6].

❓ Predict Output

expert

Bottom View Output for Complex Tree with Overlapping Nodes

What is the output of the bottom view function for the following tree?

DSA Typescript

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

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

  while (queue.length > 0) {
    const {node, hd} = queue.shift()!;
    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.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.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.right = new Node(8);
root.right.left.left = new Node(9);

console.log(bottomView(root));

A [4, 9, 6, 3, 7]

B [8, 5, 9, 6, 7]

C [4, 8, 5, 6, 7]

D [4, 2, 9, 6, 7]

💡 Hint

Track horizontal distances carefully and note the last node at each hd during level order traversal.

Horizontal distances and last nodes: hd=-2:4, hd=-1:9 (2 overwritten by 8 then 9), hd=0:6 (1 overwritten by 5 then 6), hd=1:3, hd=2:7.

Sorted by hd ascending: [4, 9, 6, 3, 7].