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

Mental Model

A Binary Search Tree (BST) keeps data in order so you can find items in sorted sequence, while a Hash Map finds items fast but does not keep order.

Analogy: Think of a BST like a sorted bookshelf where books are arranged by title, so you can quickly find books in order. A Hash Map is like a pile of books with labels, where you find a book instantly by its label but the pile is messy and unordered.

BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Hash Map:
[0]: null
[1]: (key:1, value)
[2]: (key:2, value)
[3]: (key:3, value)
[4]: (key:4, value)
[5]: (key:5, value)
[6]: (key:6, value)
[7]: (key:7, value)

Dry Run Walkthrough

Input: Insert keys 4, 2, 6, 1, 3, 5, 7 into BST and Hash Map

Goal: Show how BST keeps keys ordered for traversal and Hash Map stores keys unordered but with fast access

Step 1: Insert 4 as root in BST; add (4) in Hash Map at index 4

BST: 4
Hash Map: [null, null, null, null, 4, null, null, null, null, null]

Why: Start BST with root; Hash Map stores key at hashed index

Step 2: Insert 2 in BST left of 4; add (2) in Hash Map at index 2

BST:
  4
 /
2
Hash Map: [null, null, 2, null, 4, null, null, null, null, null]

Why: 2 is less than 4, goes left in BST; Hash Map stores at hash index

Step 3: Insert 6 in BST right of 4; add (6) in Hash Map at index 6

BST:
  4
 / \
2   6
Hash Map: [null, null, 2, null, 4, null, 6, null, null, null]

Why: 6 is greater than 4, goes right in BST; Hash Map stores at hash index

Step 4: Insert 1 in BST left of 2; add (1) in Hash Map at index 1

BST:
    4
   / \
  2   6
 /
1
Hash Map: [null, 1, 2, null, 4, null, 6, null, null, null]

Why: 1 less than 2, goes left; Hash Map stores at hash index

Step 5: Insert 3 in BST right of 2; add (3) in Hash Map at index 3

BST:
    4
   / \
  2   6
 / \
1   3
Hash Map: [null, 1, 2, 3, 4, null, 6, null, null, null]

Why: 3 greater than 2, goes right; Hash Map stores at hash index

Step 6: Insert 5 in BST left of 6; add (5) in Hash Map at index 5

BST:
    4
   / \
  2   6
 / \  /
1   3 5
Hash Map: [null, 1, 2, 3, 4, 5, 6, null, null, null]

Why: 5 less than 6, goes left; Hash Map stores at hash index

Step 7: Insert 7 in BST right of 6; add (7) in Hash Map at index 7

BST:
    4
   / \
  2   6
 / \ / \
1  3 5  7
Hash Map: [null, 1, 2, 3, 4, 5, 6, 7, null, null]

Why: 7 greater than 6, goes right; Hash Map stores at hash index

Result:

BST in-order traversal: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Hash Map keys stored unordered but accessible instantly by key

Annotated Code

DSA Typescript

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

class BST {
  root: TreeNode | null = null;

  insert(key: number): void {
    this.root = this._insert(this.root, key);
  }

  private _insert(node: TreeNode | null, key: number): TreeNode {
    if (node === null) return new TreeNode(key); // create new node
    if (key < node.key) node.left = this._insert(node.left, key); // go left
    else node.right = this._insert(node.right, key); // go right
    return node;
  }

  inorder(): number[] {
    const result: number[] = [];
    this._inorder(this.root, result);
    return result;
  }

  private _inorder(node: TreeNode | null, result: number[]): void {
    if (node === null) return;
    this._inorder(node.left, result); // traverse left subtree
    result.push(node.key); // visit node
    this._inorder(node.right, result); // traverse right subtree
  }
}

class HashMap {
  size: number;
  buckets: Array<number | null>;

  constructor(size: number) {
    this.size = size;
    this.buckets = new Array(size).fill(null);
  }

  private hash(key: number): number {
    return key % this.size; // simple mod hash
  }

  insert(key: number): void {
    const index = this.hash(key);
    this.buckets[index] = key; // overwrite for simplicity
  }

  getBuckets(): Array<number | null> {
    return this.buckets;
  }
}

// Driver code
const keys = [4, 2, 6, 1, 3, 5, 7];
const bst = new BST();
const hashMap = new HashMap(10);

for (const key of keys) {
  bst.insert(key);
  hashMap.insert(key);
}

console.log('BST inorder traversal:', bst.inorder().join(' -> ') + ' -> null');
console.log('Hash Map buckets:', hashMap.getBuckets());

if (node === null) return new TreeNode(key);

create new node when reached null position

if (key < node.key) node.left = this._insert(node.left, key);

go left if key smaller

else node.right = this._insert(node.right, key);

go right if key greater or equal

this._inorder(node.left, result);

traverse left subtree first for sorted order

result.push(node.key);

visit current node

this._inorder(node.right, result);

traverse right subtree next

const index = this.hash(key);

compute hash index for key

this.buckets[index] = key;

store key at hashed index (overwrite for simplicity)

Output

BST inorder traversal: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null

Hash Map buckets: [ null, 1, 2, 3, 4, 5, 6, 7, null, null ]

Complexity Analysis

Time: O(n log n) for BST insertion on average because each insert takes O(log n) and we do n inserts; O(n) for Hash Map insertion because each insert is O(1) on average

Space: O(n) for both BST and Hash Map because they store all n keys

vs Alternative: BST allows ordered traversal and range queries efficiently, while Hash Map provides faster direct access but no order; BST can degrade to O(n) insertion if unbalanced

Edge Cases

Empty input keys

BST remains empty; Hash Map buckets remain null

DSA Typescript

if (node === null) return new TreeNode(key);

Duplicate keys

BST inserts duplicates to right subtree; Hash Map overwrites existing key at hash index

DSA Typescript

else node.right = this._insert(node.right, key);

Hash collisions

Current Hash Map overwrites existing key at index, losing previous key (simple implementation)

DSA Typescript

this.buckets[index] = key;

When to Use This Pattern

When you need to store data with quick access and also want to keep it sorted or do range queries, consider BST; if order doesn't matter and you want fastest lookup, use Hash Map.

Common Mistakes

Mistake: Assuming Hash Map keeps keys in order
Fix: Remember Hash Map stores keys based on hash, so order is not guaranteed

Mistake: Not handling duplicates in BST properly
Fix: Decide and implement consistent rule for duplicates, e.g., always insert duplicates to right subtree

Summary

BST stores keys in order allowing sorted traversal; Hash Map stores keys for fast access without order.

Use BST when you need ordered data or range queries; use Hash Map when you need fastest key lookup without order.

The key insight is BST maintains order by structure, Hash Map uses hashing for speed but loses order.

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