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].

Practice

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

easy

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

B. Nodes visible when the tree is viewed from the top

C. Nodes visible when the tree is viewed from the bottom

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

Solution

1. Step 1: Understand the bottom view concept

   The bottom view of a binary tree includes nodes that are visible when looking at the tree from below, meaning the lowest nodes at each horizontal distance.

2. Step 2: Compare with other views

   Top view shows nodes visible from above, left view from left side, right view from right side. Bottom view is distinct as it shows the lowest nodes at each horizontal position.

3. Final Answer:

   Nodes visible when the tree is viewed from the bottom -> Option C

4. Quick Check:

   Bottom view = visible nodes from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal distance [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking bottom view shows all leaf nodes
• Mixing bottom view with left or right side views

2. Which TypeScript data structure is best suited to store nodes by their horizontal distance when computing the bottom view?

easy

A. Array

B. Map (key-value pairs)

C. Set

D. Stack

Solution

1. Step 1: Identify the need to map horizontal distances

   We need to associate each horizontal distance with the node visible at that distance in the bottom view.

2. Step 2: Choose a data structure for key-value mapping

   A Map allows storing keys (horizontal distances) with corresponding node values, enabling easy updates and retrieval.

3. Final Answer:

   Map (key-value pairs) -> Option B

4. Quick Check:

   Use Map for horizontal distance to node mapping [OK]

Hint: Use Map to link horizontal distance with nodes [OK]

Common Mistakes:

• Using Array which is index-based, not key-based
• Using Set which stores unique values but no keys
• Using Stack which is LIFO, not suitable for mapping

3. What is the output bottom view of the binary tree represented by the following code?

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

const root = new Node(20,
  new Node(8,
    new Node(5),
    new Node(3, null, new Node(10))
  ),
  new Node(22, null, new Node(25))
);

medium

A. [5, 8, 3, 10, 25]

B. [5, 10, 3, 22, 25]

C. [8, 3, 10, 22, 25]

D. [5, 3, 10, 22, 25]

Solution

1. Step 1: Assign horizontal distances and track nodes

   Horizontal distances: 20(0), 8(-1), 22(1), 5(-2), 3(0), 10(1), 25(2). Level order traversal order: 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(1). For bottom view, the last node encountered at each hd.

2. Step 2: Determine bottom view nodes by horizontal distance

   hd -2:5; -1:8; 0:3 (overwrites 20); 1:10 (overwrites 22); 2:25. Sorted left-to-right: [5, 8, 3, 10, 25].

3. Final Answer:

   [5, 8, 3, 10, 25] -> Option A

4. Quick Check:

   Bottom view nodes = [5, 8, 3, 10, 25] [OK]

Hint: Track last node at each horizontal distance [OK]

Common Mistakes:

• Choosing first node at horizontal distance instead of last
• Mixing horizontal distances incorrectly
• Ignoring right child nodes at same horizontal distance

4. Identify the bug in this TypeScript code snippet for bottom view of a binary tree:

function bottomView(root: Node | null): number[] {
  if (!root) return [];
  const map = new Map();
  const queue: Array<{node: Node; hd: number}> = [{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 Array.from(map.values());
}

medium

A. It only stores the first node at each horizontal distance, not the bottom-most

B. It uses shift() which is inefficient for queue

C. It does not check if root is null

D. It returns keys instead of values from the map

Solution

1. Step 1: Analyze map update condition

   The code sets map value only if horizontal distance is not present, so it keeps the first node at that distance.

2. Step 2: Understand bottom view requirement

   Bottom view requires the last (bottom-most) node at each horizontal distance, so map should update value every time a node at that hd is found.

3. Final Answer:

   It only stores the first node at each horizontal distance, not the bottom-most -> Option A

4. Quick Check:

   Bottom view needs last node per hd, code stores first [OK]

Hint: Update map value for every node at horizontal distance [OK]

Common Mistakes:

• Not updating map for later nodes at same horizontal distance
• Confusing top view logic with bottom view
• Ignoring null root check (though present here)

5. Given a binary tree where multiple nodes share the same horizontal distance and depth, how should the bottom view algorithm decide which node to display?

hard

A. Display the node with the smallest value at that horizontal distance

B. Display the node with the largest depth but smallest horizontal distance

C. Display the node that appears first in level order traversal at that horizontal distance

D. Display the node that appears last in level order traversal at that horizontal distance

Solution

1. Step 1: Understand node selection criteria for bottom view

   Bottom view shows the lowest node at each horizontal distance. When multiple nodes share horizontal distance and depth, the one encountered last in level order traversal is visible.

2. Step 2: Clarify why last in level order matters

   Level order visits nodes top to bottom, left to right. The last node at a horizontal distance overwrites previous ones, ensuring bottom-most visibility.

3. Final Answer:

   Display the node that appears last in level order traversal at that horizontal distance -> Option D

4. Quick Check:

   Bottom view = last node per hd in level order [OK]

Hint: Choose last node at horizontal distance in level order [OK]

Common Mistakes:

• Choosing node by value instead of position
• Selecting first node instead of last at horizontal distance
• Confusing horizontal distance with depth