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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why choose a BST over a Hash Map for ordered data?

Which of the following is the main reason to prefer a Binary Search Tree (BST) instead of a Hash Map when you need to keep data in order?

A BST keeps data sorted and allows in-order traversal to get ordered data easily.

B BST uses less memory than Hash Map in all cases.

C BST has faster average lookup time than Hash Map.

D BST automatically handles duplicate keys better than Hash Map.

💡 Hint

Think about how you get sorted data from each structure.

BST stores data in a way that allows in-order traversal to retrieve sorted data. Hash Maps do not maintain order.

❓ Predict Output

intermediate

Output of in-order traversal on BST

What is the output of the in-order traversal of this BST?

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function inorder(root, result = []) {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

// Construct BST
const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.right = new Node(18);

console.log(inorder(root));

A [18, 15, 10, 7, 5, 3]

B [10, 5, 3, 7, 15, 18]

C [3, 5, 7, 10, 15, 18]

D [5, 3, 7, 10, 15, 18]

💡 Hint

In-order traversal visits left subtree, node, then right subtree.

In-order traversal of BST visits nodes in ascending order.

❓ Predict Output

advanced

Hash Map key order after insertions

What will be the order of keys when iterating over this JavaScript Map?

DSA Javascript

const map = new Map();
map.set('b', 2);
map.set('a', 1);
map.set('c', 3);

const keys = [];
for (const key of map.keys()) {
  keys.push(key);
}
console.log(keys);

A []

B ["b", "a", "c"]

C ["c", "b", "a"]

D ["a", "b", "c"]

💡 Hint

JavaScript Map preserves insertion order of keys.

Map keys are iterated in the order they were added.

🧠 Conceptual

advanced

Time complexity trade-offs between BST and Hash Map

Which statement correctly compares average time complexities of search operations in a balanced BST and a Hash Map?

A Balanced BST search is O(log n), Hash Map search is O(1) on average.

B Balanced BST search is O(n), Hash Map search is O(log n) on average.

C Balanced BST search is O(1), Hash Map search is O(log n) on average.

D Both Balanced BST and Hash Map have O(n) search time on average.

💡 Hint

Think about how balanced trees and hash maps organize data.

Balanced BSTs have logarithmic search time; Hash Maps have constant average search time.

🚀 Application

expert

Choosing data structure for range queries on ordered data

You need to store a large set of numbers and frequently perform range queries (e.g., find all numbers between 10 and 50). Which data structure is best suited for this task?

A Stack, because it allows easy access to the last inserted number.

B Hash Map, because it provides constant time lookups for any number.

C Unsorted Array, because it uses less memory and is faster for insertions.

D Balanced Binary Search Tree, because it supports efficient range queries via in-order traversal.

💡 Hint

Consider which structure allows ordered traversal and efficient range filtering.

Balanced BSTs keep data sorted and allow efficient range queries by traversing only relevant parts.

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