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

Concept Flow - BST vs Hash Map Trade-offs for Ordered Data

Start: Need to store key-value pairs

↓

Is order important?

No→Use Hash Map

Yes↓

Do you need fast search, insert, delete?

Yes↓

Use Balanced BST (e.g., AVL, Red-Black)

↓

Supports ordered traversal, range queries

↓

Trade-offs: BST slower average insert/search than Hash Map but ordered

↓

Hash Map

↓

Fast average insert/search/delete

↓

No order guaranteed

↓

Cannot do range queries efficiently

This flow shows decision points when choosing between BST and Hash Map for ordered data, highlighting order importance and operation speed trade-offs.

Execution Sample

DSA Typescript

interface Node {
  key: number;
  value: string;
  left?: Node;
  right?: Node;
}

// Insert in BST preserving order
function insertBST(root: Node | undefined, key: number, value: string): Node {
  if (!root) return { key, value };
  if (key < root.key) root.left = insertBST(root.left, key, value);
  else root.right = insertBST(root.right, key, value);
  return root;
}

This code inserts key-value pairs into a BST, preserving order for efficient ordered operations.

Execution Table

Step	Operation	Nodes in BST (key:value)	Pointer Changes	Visual State
1	Insert (10, 'A')	10:A	root = new node(10)	10:A
2	Insert (5, 'B')	10:A, 5:B	root.left = new node(5)	10:A / 5:B
3	Insert (15, 'C')	10:A, 5:B, 15:C	root.right = new node(15)	10:A / \ 5:B 15:C
4	Insert (7, 'D')	10:A, 5:B, 7:D, 15:C	5:B.right = new node(7)	10:A / \ 5:B 15:C \ 7:D
5	Insert (3, 'E')	10:A, 5:B, 3:E, 7:D, 15:C	5:B.left = new node(3)	10:A / \ 5:B 15:C / \ 3:E 7:D
6	Search key=7	Same as above	Traverse root->left->right	Pointer at node 7:D
7	Hash Map Insert (10:'A')	N/A	hash[10] = 'A'	{10:'A'}
8	Hash Map Insert (5:'B')	N/A	hash[5] = 'B'	{10:'A',5:'B'}
9	Hash Map Insert (15:'C')	N/A	hash[15] = 'C'	{10:'A',5:'B',15:'C'}
10	Hash Map Search key=7	N/A	hash[7] undefined	No value found
11	End	N/A	No more operations	BST and Hash Map states stable

💡 All insertions and searches complete; BST maintains order, Hash Map does not.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10
BST Root	undefined	Node(10:A)	Node(10:A)	Node(10:A)	Node(10:A)	Node(10:A)	Node(10:A)	Node(10:A)	Node(10:A)	Node(10:A)	Node(10:A)
BST Nodes	empty	10:A	10:A,5:B	10:A,5:B,15:C	10:A,5:B,15:C,7:D	10:A,5:B,15:C,7:D,3:E	Same	Same	Same	Same	Same
Hash Map	empty	empty	empty	empty	empty	empty	empty	{10:'A'}	{10:'A',5:'B'}	{10:'A',5:'B',15:'C'}	{10:'A',5:'B',15:'C'}
Search Result (key=7)	N/A	N/A	N/A	N/A	N/A	N/A	Node(7:D)	N/A	N/A	N/A	undefined

Key Moments - 3 Insights

Why does BST keep keys ordered but Hash Map does not?

BST inserts nodes based on key comparison, placing smaller keys left and larger keys right (see steps 2-5 in execution_table). Hash Map uses hashing which scatters keys without order (see steps 7-9).

Why is searching key=7 successful in BST but fails in Hash Map?

BST traversal follows left/right pointers to find key=7 (step 6). Hash Map search for key=7 returns undefined because key=7 was never inserted (step 10).

What is the trade-off in operation speed between BST and Hash Map?

Hash Map offers faster average insert/search (steps 7-9) but no order. BST is slower due to pointer traversal (steps 2-6) but keeps keys ordered for range queries.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, where is the new node with key=7 inserted?

A As left child of node 5

B As right child of node 5

C As left child of node 10

D As right child of node 10

💡 Hint

Check 'Pointer Changes' and 'Visual State' columns at step 4 showing 5:B.right = new node(7)

At which step does the Hash Map contain the key 15?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look at Hash Map insertions in execution_table steps 7-9; key 15 is added at step 9

According to variable_tracker, what is the search result for key=7 after step 6?

A undefined

B Node with key=7 and value 'D'

C Node with key=5 and value 'B'

D Node with key=10 and value 'A'

💡 Hint

Check 'Search Result (key=7)' row in variable_tracker after step 6

Concept Snapshot

BST vs Hash Map Trade-offs:
- BST keeps keys ordered using left/right pointers
- Supports ordered traversal and range queries
- Insert/search slower due to tree traversal
- Hash Map offers fast average insert/search
- Hash Map does not maintain order
- Choose BST if order matters, Hash Map for speed without order

Full Transcript

This lesson compares Binary Search Trees (BST) and Hash Maps for storing key-value pairs when order matters. BST inserts keys by comparing and placing smaller keys to the left and larger to the right, keeping data ordered. Hash Maps use hashing to store keys quickly but lose order. The execution table shows inserting keys 10, 5, 15, 7, and 3 into a BST, building a tree structure. Searching key 7 in BST follows pointers to find the node. Hash Map inserts keys 10, 5, and 15 quickly but searching key 7 fails as it was not inserted. Variable tracker shows how BST nodes and Hash Map entries change step by step. Key moments clarify why BST keeps order, why search differs, and the speed trade-offs. Visual quiz questions test understanding of insertion positions, Hash Map contents, and search results. The concept snapshot summarizes when to use each structure based on order needs and operation speed.

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