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.