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.