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

Mental Model

A Binary Search Tree (BST) keeps data sorted and allows ordered operations, while a Hash Map stores data for fast lookup but loses order.

Analogy: Think of a BST like a sorted bookshelf where books are arranged by title, so you can find books in order or find the next one easily. A Hash Map is like a pile of books with labels, so you find a book quickly by label but can't easily find the next or previous book in order.

BST:
      5
     / \
    3   7
   / \   \
  2   4   8

Hash Map:
[ '2': bookA, '3': bookB, '4': bookC, '5': bookD, '7': bookE, '8': bookF ]

Dry Run Walkthrough

Input: Data: keys 2,3,4,5,7,8; search for key 4 and find next key after 4

Goal: Show how BST supports ordered search and next element retrieval, while Hash Map supports fast search but not ordered next element

Step 1: Search for key 4 in BST starting at root 5

5 -> [curr->3] -> 7
3 -> [curr->4] -> null
Found key 4

Why: We move left from 5 to 3 because 4 < 5, then right from 3 to 4 because 4 > 3

Step 2: Find next key after 4 in BST

4 has no right child, move up to parent 3, then up to 5
Next key is 5

Why: In BST, next key is smallest key greater than current; since 4 has no right child, we go up to find next larger key

Step 3: Search for key 4 in Hash Map

[ '2': val, '3': val, '4': val, '5': val, '7': val, '8': val ]
Found key 4 directly

Why: Hash Map uses key hashing for direct access, so search is O(1)

Step 4: Try to find next key after 4 in Hash Map

No inherent order in Hash Map keys
Cannot find next key without extra sorting

Why: Hash Map does not keep keys sorted, so ordered operations are not supported efficiently

Result:

BST final state: 2 -> 3 -> 4 -> 5 -> 7 -> 8 (in order)
Hash Map final state: keys stored unordered
Answer: BST supports ordered next key (5), Hash Map does not

Annotated Code

DSA Javascript

class BSTNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(key) {
    const newNode = new BSTNode(key);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let curr = this.root;
    while (true) {
      if (key < curr.key) {
        if (!curr.left) {
          curr.left = newNode;
          newNode.parent = curr;
          break;
        }
        curr = curr.left;
      } else {
        if (!curr.right) {
          curr.right = newNode;
          newNode.parent = curr;
          break;
        }
        curr = curr.right;
      }
    }
  }

  search(key) {
    let curr = this.root;
    while (curr) {
      if (key === curr.key) return curr;
      curr = key < curr.key ? curr.left : curr.right;
    }
    return null;
  }

  next(node) {
    if (node.right) {
      let curr = node.right;
      while (curr.left) curr = curr.left;
      return curr;
    }
    let curr = node;
    while (curr.parent && curr === curr.parent.right) {
      curr = curr.parent;
    }
    return curr.parent;
  }
}

class HashMap {
  constructor() {
    this.map = new Map();
  }

  insert(key, value) {
    this.map.set(key, value);
  }

  search(key) {
    return this.map.has(key) ? this.map.get(key) : null;
  }

  next(key) {
    // Hash Map does not support ordered next key
    return null;
  }
}

// Driver code
const bst = new BST();
[5,3,7,2,4,8].forEach(k => bst.insert(k));
const node = bst.search(4);
const nextNode = node ? bst.next(node) : null;

const hashMap = new HashMap();
[2,3,4,5,7,8].forEach(k => hashMap.insert(k, `val${k}`));
const hashVal = hashMap.search(4);
const hashNext = hashMap.next(4);

console.log(`BST search 4: ${node ? node.key : 'not found'}`);
console.log(`BST next after 4: ${nextNode ? nextNode.key : 'none'}`);
console.log(`HashMap search 4: ${hashVal}`);
console.log(`HashMap next after 4: ${hashNext === null ? 'none' : hashNext}`);

while (true) { if (key < curr.key) { ... } else { ... } }

Traverse BST to find correct insert position

while (curr) { if (key === curr.key) return curr; curr = key < curr.key ? curr.left : curr.right; }

Traverse BST to find node with key

if (node.right) { let curr = node.right; while (curr.left) curr = curr.left; return curr; }

Find next node in BST by going to right subtree's leftmost node

while (curr.parent && curr === curr.parent.right) { curr = curr.parent; } return curr.parent;

If no right child, move up to find next larger ancestor

return this.map.has(key) ? this.map.get(key) : null;

Hash Map direct key lookup

return null;

Hash Map does not support ordered next key

Output

BST search 4: 4

BST next after 4: 5

HashMap search 4: val4

HashMap next after 4: none

Complexity Analysis

Time: BST operations are O(h) where h is tree height (average O(log n)), Hash Map operations are O(1) average for search but no ordered operations

Space: Both use O(n) space to store n elements

vs Alternative: BST supports ordered operations with moderate cost, Hash Map is faster for exact key lookup but cannot do ordered queries efficiently

Edge Cases

Empty BST or Hash Map

Search returns null, next returns null

DSA Javascript

if (!this.root) { this.root = newNode; return; }

Search for key not present

Returns null in both BST and Hash Map

DSA Javascript

while (curr) { if (key === curr.key) return curr; curr = key < curr.key ? curr.left : curr.right; }

Next key for largest key in BST

Returns null because no larger key exists

DSA Javascript

while (curr.parent && curr === curr.parent.right) { curr = curr.parent; } return curr.parent;

When to Use This Pattern

When a problem needs both fast key lookup and ordered data traversal, consider BST for order and Hash Map for speed; knowing their trade-offs helps choose the right structure.

Common Mistakes

Mistake: Assuming Hash Map can provide next ordered key efficiently
Fix: Remember Hash Map keys are unordered; use BST or other ordered structures for next key queries

Summary

BST keeps data sorted and supports ordered operations like finding the next key.

Use BST when you need ordered traversal or range queries; use Hash Map for fast exact key lookup.

The key insight is BST maintains order with pointers, while Hash Map uses hashing for speed but loses order.

Practice

1. Which data structure is best suited when you need to maintain elements in a 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 need for sorted order

   Maintaining elements in sorted order requires a structure that keeps data sorted as elements are added or removed.

2. Step 2: Compare BST and Hash Map for sorted data

   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 data + range queries = BST [OK]

Hint: Sorted order needs BST, hash maps don't keep order [OK]

Common Mistakes:

• Thinking hash maps keep data sorted
• Confusing stack or queue with sorted structures
• Assuming hash maps support range queries

2. Which of the following is the correct way to declare a Hash Map (Map) in JavaScript?

easy

A. const map = {};

B. const map = Map();

C. const map = new HashMap();

D. const map = new Map();

Solution

1. Step 1: Recall JavaScript Map syntax

   JavaScript uses the Map object with the syntax new Map() to create a hash map.

2. Step 2: Check each option

   const map = new Map(); uses new Map(), which is correct. const map = Map(); misses 'new'. const map = {}; creates a plain object, not a Map. const map = new HashMap(); uses a non-existent HashMap class.

3. Final Answer:

   const map = new Map(); -> Option D

4. Quick Check:

   Map creation syntax = new Map() [OK]

Hint: Use new Map() to create a hash map in JavaScript [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using plain objects instead of Map
• Assuming HashMap class exists in JS

3. Consider the following JavaScript code using a BST class with insert and inorderTraversal methods:

const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
console.log(bst.inorderTraversal());

What will be the output?

medium

A. [10, 5, 15]

B. [5, 10, 15]

C. [15, 10, 5]

D. [5, 15, 10]

Solution

1. Step 1: Understand inorder traversal of BST

   Inorder traversal visits nodes in ascending order: left subtree, root, right subtree.

2. Step 2: Trace insertion and traversal

   Insert 10 as root, 5 to left, 15 to right. Inorder traversal visits 5, then 10, then 15.

3. Final Answer:

   [5, 10, 15] -> Option B

4. Quick Check:

   Inorder traversal = sorted nodes [OK]

Hint: Inorder traversal of BST returns sorted array [OK]

Common Mistakes:

• Assuming insertion order equals traversal order
• Confusing preorder or postorder with inorder
• Expecting hash map order instead of BST order

4. The following code attempts to use a Hash Map to maintain sorted keys. What is the main issue?

const map = new Map();
map.set(3, 'c');
map.set(1, 'a');
map.set(2, 'b');
console.log([...map.keys()]);

medium

A. Keys are not guaranteed to be in sorted order

B. Map keys must be strings only

C. Map cannot store numbers as keys

D. map.set() syntax is incorrect

Solution

1. Step 1: Understand Map key order behavior

   JavaScript Map preserves insertion order, not sorted order of keys.

2. Step 2: Analyze the output of keys()

   Keys will be in insertion order [3,1,2], not sorted [1,2,3].

3. Final Answer:

   Keys are not guaranteed to be in sorted order -> Option A

4. Quick Check:

   Map keys order = insertion order, not sorted [OK]

Hint: Map keys keep insertion order, not sorted order [OK]

Common Mistakes:

• Thinking Map sorts keys automatically
• Believing Map keys must be strings
• Confusing Map with Object key behavior

5. You need to store a large dataset with frequent insertions and lookups by key, but also require fast retrieval of all keys in sorted order. Which approach is best?

hard

A. Use an Array and perform linear search

B. Use a Hash Map alone and sort keys on demand

C. Use a Balanced BST to store keys and values

D. Use a Queue to maintain insertion order

Solution

1. Step 1: Analyze requirements for insertions, lookups, and sorted retrieval

   Frequent insertions and lookups need efficient operations; sorted retrieval requires order maintenance.

2. Step 2: Compare data structures for these needs

   Hash Map offers fast lookups but no order; sorting keys on demand is costly. Balanced BST maintains sorted order and supports efficient insertions and lookups.

3. Final Answer:

   Use a Balanced BST to store keys and values -> Option C

4. Quick Check:

   Balanced BST = fast insert, lookup + sorted keys [OK]

Hint: Balanced BST combines fast lookup and sorted order [OK]

Common Mistakes:

• Choosing hash map without sorting cost consideration
• Using array causing slow lookups
• Using queue which doesn't support sorted retrieval