BST vs Hash Map Trade-offs for Ordered Data in DSA Typescript - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why choose a BST over a Hash Map for ordered data?

Which reason best explains why a Binary Search Tree (BST) is preferred over a Hash Map when you need to maintain data in order?

A BST keeps elements sorted, allowing in-order traversal to get data in ascending order.

B BST has faster average lookup time than Hash Map.

C Hash Map automatically sorts keys, so BST is unnecessary.

D BST uses less memory than Hash Map in all cases.

💡 Hint

Think about how each data structure stores and accesses data.

BST stores data in a way that keeps keys sorted, so you can easily get ordered data by traversing it. Hash Maps do not maintain order.

❓ Predict Output

intermediate

Output of in-order traversal vs Hash Map iteration

Given the following data inserted in this order: 5, 3, 7 into a BST and a Hash Map, what is the output of an in-order traversal of the BST and iteration over the Hash Map?

DSA Typescript

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

const hashMap = new Map();
hashMap.set(5, 'five');
hashMap.set(3, 'three');
hashMap.set(7, 'seven');

// Output BST in-order traversal keys
// Output Hash Map keys iteration order

A

BST in-order: 7 -> 5 -> 3
Hash Map iteration: 7, 5, 3

B

BST in-order: 5 -> 3 -> 7
Hash Map iteration: 3, 5, 7

C

BST in-order: 3 -> 5 -> 7
Hash Map iteration: 5, 3, 7

D

BST in-order: 3 -> 7 -> 5
Hash Map iteration: 5, 7, 3

💡 Hint

Remember how in-order traversal works and how Map preserves insertion order.

In-order traversal of BST visits nodes in ascending order: 3, 5, 7. Map iteration preserves insertion order: 5, 3, 7.

🔧 Debug

advanced

Why does this BST code fail to maintain order?

Consider this simplified BST insert code snippet. Why does it fail to keep the tree ordered?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(val: number) {
    if (!this.root) {
      this.root = new Node(val);
      return;
    }
    let current = this.root;
    while (current) {
      if (val < current.val) {
        current.left = new Node(val);
        break;
      } else {
        current.right = new Node(val);
        break;
      }
    }
  }
}

A It overwrites left or right child without checking if they are null, losing existing nodes.

B It uses a while loop but never updates current, causing infinite loop.

C It inserts duplicates without checking for equality.

D It does not create new nodes for values greater than root.

💡 Hint

Look at how the left and right children are assigned inside the loop.

The code assigns new nodes directly to left or right child without checking if those children already exist, so it overwrites existing subtrees and breaks the BST property.

🚀 Application

advanced

Choosing data structure for range queries on ordered data

You need to frequently find all keys between two values (range queries) in a large dataset. Which data structure is best suited?

A Stack, because it stores elements in order of insertion.

B Hash Map, because it has constant time lookup for all keys.

C Array, because sorting once is enough for all queries.

D Binary Search Tree, because it supports efficient in-order traversal for range queries.

💡 Hint

Think about which structure allows ordered traversal and efficient range filtering.

BST allows in-order traversal which visits keys in sorted order, making range queries efficient. Hash Maps and stacks do not maintain order, and arrays require sorting each time if modified.

❓ Predict Output

expert

Output after mixed BST and Hash Map operations

Given the following operations, what is the final output of the BST in-order traversal and the Hash Map keys iteration?

DSA Typescript

const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(12);
bst.insert(18);

const hashMap = new Map();
hashMap.set(10, 'ten');
hashMap.set(5, 'five');
hashMap.set(15, 'fifteen');
hashMap.delete(5);
hashMap.set(12, 'twelve');
hashMap.set(18, 'eighteen');

// Print BST in-order traversal keys
// Print Hash Map keys iteration order

A

BST in-order: 5 -> 10 -> 12 -> 15 -> 18
Hash Map iteration: 5, 10, 15, 12, 18

B

BST in-order: 5 -> 10 -> 12 -> 15 -> 18
Hash Map iteration: 10, 15, 12, 18

C

BST in-order: 10 -> 5 -> 12 -> 15 -> 18
Hash Map iteration: 5, 10, 15, 12, 18

D

BST in-order: 5 -> 10 -> 15 -> 12 -> 18
Hash Map iteration: 10, 5, 15, 12, 18

💡 Hint

Remember that deleting a key from Map removes it from iteration, and BST in-order traversal is sorted.

BST in-order traversal visits nodes in ascending order: 5, 10, 12, 15, 18. Hash Map iteration preserves insertion order except deleted keys are removed, so keys are 10, 15, 12, 18.

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