BST vs Hash Map Trade-offs for Ordered Data in DSA Typescript - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a value into a Binary Search Tree (BST).

DSA Typescript

function insertBST(root: TreeNode | null, val: number): TreeNode {
  if (root === null) {
    return new TreeNode(val);
  }
  if (val [1] root.val) {
    root.left = insertBST(root.left, val);
  } else {
    root.right = insertBST(root.right, val);
  }
  return root;
}

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

A>

B<

C===

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' causes wrong placement in BST.

Using '===' will never insert properly.

In a BST, values less than the current node go to the left subtree.

2fill in blank

medium

Complete the code to check if a key exists in a Hash Map.

DSA Typescript

function hasKey(map: Map<string, number>, key: string): boolean {
  return map.[1](key);
}

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

Aget

Bcontains

Cfind

Dhas

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'get' returns the value or undefined, not a boolean.

Using 'find' or 'contains' are not valid Map methods.

The has method checks if a key exists in a Map.

3fill in blank

hard

Fix the error in the code to find the minimum value in a BST.

DSA Typescript

function findMin(root: TreeNode | null): number | null {
  if (root === null) return null;
  let current = root;
  while (current.[1] !== null) {
    current = current.left;
  }
  return current.val;
}

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

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'right' will find the maximum, not minimum.

Using 'parent' or 'child' are invalid properties.

The minimum value in a BST is found by going left until no more left child exists.

4fill in blank

hard

Fill both blanks to create a function that returns keys in sorted order from a BST.

DSA Typescript

function inorderTraversal(root: TreeNode | null, result: number[] = []): number[] {
  if (root !== null) {
    inorderTraversal(root.[1], result);
    result.push(root.val);
    inorderTraversal(root.[2], result);
  }
  return result;
}

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

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping left and right changes the order.

Using 'parent' or 'child' causes errors.

Inorder traversal visits left subtree, then node, then right subtree, producing sorted keys.

5fill in blank

hard

Fill all three blanks to create a function that counts keys in a Hash Map greater than a threshold.

DSA Typescript

function countGreaterThan(map: Map<string, number>, threshold: number): number {
  let count = 0;
  for (const [1] of map.entries()) {
    const [key, value] = [2];
    if (value [3] threshold) {
      count++;
    }
  }
  return count;
}

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

Aentry

B>

C<

Ditem

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' counts values less than threshold.

Using wrong variable names causes errors.

We iterate over entries, unpack each entry, and count values greater than threshold.

Practice

1. Which data structure is best suited when you need to maintain elements in sorted order and perform range queries efficiently?

easy

A. Binary Search Tree (BST)

B. Hash Map

C. Stack

D. Queue

Solution

1. Step 1: Understand the requirement for sorted order and range queries

   Maintaining sorted order and performing range queries require a data structure that keeps elements ordered.

2. Step 2: Compare BST and Hash Map capabilities

   BST keeps elements sorted and supports efficient range queries, while Hash Map does not maintain order.

3. Final Answer:

   Binary Search Tree (BST) -> Option A

4. Quick Check:

   Sorted order + range queries = BST [OK]

Hint: Sorted order needs BST, not Hash Map [OK]

Common Mistakes:

• Thinking Hash Map maintains order
• Confusing range queries with simple lookups
• Assuming Stack or Queue can maintain sorted data

2. Which of the following is the correct TypeScript syntax to declare a Hash Map with string keys and number values?

easy

A. const map: Map = new Map();

B. const map: HashMap = new HashMap();

C. const map: Object = {};

D. const map: Map = new Map();

Solution

1. Step 1: Identify the correct TypeScript Map declaration

   TypeScript uses Map for hash maps, where K is key type and V is value type.

2. Step 2: Check each option's syntax

   const map: Map = new Map(); correctly declares a Map with string keys and number values. const map: HashMap = new HashMap(); uses a non-existent HashMap type. const map: Map = new Map(); swaps key and value types. const map: Object = {}; uses Object incorrectly.

3. Final Answer:

   const map: Map<string, number> = new Map(); -> Option D

4. Quick Check:

   Map<string, number> syntax correct [OK]

Hint: Use Map for hash maps in TypeScript [OK]

Common Mistakes:

• Using non-existent HashMap type
• Swapping key and value types
• Using plain Object without type safety

3. Consider the following TypeScript code using a BST and a Hash Map:

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

class BST {
  root: Node | null = null;
  insert(value: number) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }
  inorder(node: Node | null, result: number[]) {
    if (!node) return;
    this.inorder(node.left, result);
    result.push(node.value);
    this.inorder(node.right, result);
  }
}

const bst = new BST();
bst.insert(3);
bst.insert(1);
bst.insert(4);

const map = new Map();
map.set(3, 'three');
map.set(1, 'one');
map.set(4, 'four');

const bstResult: number[] = [];
bst.inorder(bst.root, bstResult);

console.log(bstResult);
console.log(Array.from(map.keys()));

What will be the output?

medium

A. [1, 3, 4]
[3, 1, 4]

B. [3, 1, 4]
[1, 3, 4]

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

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

Solution

1. Step 1: Trace BST inorder traversal output

   Inorder traversal visits nodes in ascending order: 1, 3, 4.

2. Step 2: Trace Map keys insertion order

   Map keys are iterated in insertion order: 3, 1, 4.

3. Final Answer:

   [1, 3, 4] [3, 1, 4] -> Option A

4. Quick Check:

   BST inorder sorted, Map keys insertion order [OK]

Hint: BST inorder sorts; Map keys keep insertion order [OK]

Common Mistakes:

• Assuming Map keys are sorted
• Confusing preorder with inorder traversal
• Expecting Map keys to be sorted automatically

4. The following TypeScript code attempts to insert keys into a BST and a Hash Map. It throws an error. What is the bug?

class BSTNode {
  value: number;
  left: BSTNode | null = null;
  right: BSTNode | null = null;
  constructor(value: number) { this.value = value; }
}

class BST {
  root: BSTNode | null = null;
  insert(value: number) {
    const newNode = new BSTNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (current) {
      if (value < current.value) {
        current = current.left!;
      } else {
        current = current.right!;
      }
    }
  }
}

const bst = new BST();
bst.insert(5);
bst.insert(3);

const map = new Map();
map.set(5, 'five');
map.set(3, 'three');

medium

A. The Map is not initialized properly.

B. Map keys must be strings, not numbers.

C. The insert method does not link new nodes to the tree, causing infinite loop or error.

D. BSTNode class is missing a parent pointer.

Solution

1. Step 1: Analyze BST insert method loop

   The loop moves current to left or right child but never assigns newNode to any child, so tree structure is not updated.

2. Step 2: Understand consequences of missing link

   Without linking newNode, the loop continues infinitely or tries to access null with non-null assertion, causing error.

3. Final Answer:

   The insert method does not link new nodes to the tree, causing infinite loop or error. -> Option C

4. Quick Check:

   Missing child assignment causes error [OK]

Hint: Always link new nodes to parent in BST insert [OK]

Common Mistakes:

• Ignoring the need to assign newNode to left/right
• Thinking Map keys must be strings
• Assuming parent pointer is mandatory

5. You need to store a large dataset of user scores that must be retrieved in sorted order and also allow fast lookup by user ID. Which combination of data structures is best to optimize both requirements?

hard

A. Use only a Hash Map with user ID as key and score as value

B. Use a Hash Map for user ID to score and a Balanced BST for scores with user IDs

C. Use only a BST with user ID as key and score as value

D. Use an array sorted by score and a Hash Map for user ID

Solution

1. Step 1: Identify requirements for sorted retrieval and fast lookup

   Sorted retrieval by score needs a structure that keeps order, fast lookup by user ID needs quick key access.

2. Step 2: Evaluate data structure combinations

   Hash Map gives O(1) lookup by user ID. Balanced BST keeps scores sorted and can store user IDs. Combining both meets both needs efficiently.

3. Step 3: Reject other options

   Only Hash Map lacks sorted order. Only BST with user ID key sorts by ID, not score. Array sorting is costly on updates.

4. Final Answer:

   Use a Hash Map for user ID to score and a Balanced BST for scores with user IDs -> Option B

5. Quick Check:

   Combine Hash Map + BST for lookup + sorted order [OK]

Hint: Combine Hash Map for lookup and BST for sorting [OK]

Common Mistakes:

• Using only one structure and missing one requirement
• Sorting array repeatedly on updates
• Using BST keyed by user ID instead of score