BST vs Hash Map Trade-offs for Ordered Data in DSA C++ - 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) over a Hash Map when you need to maintain ordered data?

A Hash Maps automatically keep data sorted without extra effort.

B BSTs keep elements sorted, allowing in-order traversal to get data in ascending order.

C Hash Maps use less memory than BSTs for storing ordered data.

D BSTs have faster average lookup time than Hash Maps.

💡 Hint

Think about how each data structure organizes data internally.

BSTs store data in a way that the left child is smaller and the right child is larger, so an in-order traversal visits elements in sorted order. Hash Maps do not maintain any order.

❓ Predict Output

intermediate

Output of in-order traversal vs Hash Map iteration

Given the following BST insertion and Hash Map insertion, what will be the output of an in-order traversal of the BST and iteration over the Hash Map?

DSA C++

struct Node {
  int val;
  Node* left;
  Node* right;
  Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void insert(Node*& root, int v) {
  if (!root) root = new Node(v);
  else if (v < root->val) insert(root->left, v);
  else insert(root->right, v);
}

void inorder(Node* root, std::vector<int>& res) {
  if (!root) return;
  inorder(root->left, res);
  res.push_back(root->val);
  inorder(root->right, res);
}

int main() {
  Node* root = nullptr;
  insert(root, 5);
  insert(root, 3);
  insert(root, 7);

  std::unordered_map<int, int> map;
  map[5] = 50;
  map[3] = 30;
  map[7] = 70;

  std::vector<int> bst_vals;
  inorder(root, bst_vals);

  std::vector<int> map_keys;
  for (auto& p : map) map_keys.push_back(p.first);

  // Print bst_vals and map_keys
}

A BST in-order: [3, 5, 7], Hash Map keys: [5, 3, 7] (order may vary)

B BST in-order: [5, 3, 7], Hash Map keys: [3, 5, 7]

C BST in-order: [7, 5, 3], Hash Map keys: [7, 5, 3]

D BST in-order: [3, 5, 7], Hash Map keys: [3, 5, 7]

💡 Hint

Remember that Hash Map iteration order is not guaranteed.

BST in-order traversal visits nodes in ascending order: 3, 5, 7. Hash Map iteration order is unpredictable and may differ each run.

🔧 Debug

advanced

Why does this BST insertion cause unbalanced tree?

Consider this code inserting sorted data into a BST. Why does it cause the tree to become unbalanced (like a linked list)?

DSA C++

void insert(Node*& root, int v) {
  if (!root) root = new Node(v);
  else if (v < root->val) insert(root->left, v);
  else insert(root->right, v);
}

int main() {
  Node* root = nullptr;
  insert(root, 1);
  insert(root, 2);
  insert(root, 3);
  insert(root, 4);
  insert(root, 5);
}

A Because the insert function uses recursion incorrectly causing infinite loops.

B Because the insert function does not check for duplicates.

C Because the root pointer is not updated after insertion.

D Because inserting sorted data always adds nodes to the right, making the tree skewed.

💡 Hint

Think about how inserting sorted values affects BST shape.

Inserting sorted values into a BST without balancing causes all nodes to be added as right children, making the tree like a linked list.

🚀 Application

advanced

Choosing data structure for range queries on ordered data

You need to store a large set of numbers and frequently query how many numbers fall within a given range [low, high]. Which data structure is best suited for this task?

A Balanced BST (like AVL or Red-Black Tree) with augmented node counts for range queries.

B Unordered Hash Map storing counts of each number.

C Simple array storing numbers unsorted.

D Stack data structure storing numbers as they arrive.

💡 Hint

Think about how to efficiently get counts of numbers in a range.

Balanced BSTs can be augmented to store subtree sizes, allowing efficient range count queries. Hash Maps and arrays do not support efficient range queries.

❓ Predict Output

expert

Output of combined BST and Hash Map operations

What is the output of the following code snippet after all operations?

DSA C++

#include <iostream>
#include <unordered_map>
#include <vector>

struct Node {
  int val;
  Node* left;
  Node* right;
  Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void insert(Node*& root, int v) {
  if (!root) root = new Node(v);
  else if (v < root->val) insert(root->left, v);
  else insert(root->right, v);
}

void inorder(Node* root, std::vector<int>& res) {
  if (!root) return;
  inorder(root->left, res);
  res.push_back(root->val);
  inorder(root->right, res);
}

int main() {
  Node* root = nullptr;
  insert(root, 10);
  insert(root, 5);
  insert(root, 15);
  insert(root, 12);
  insert(root, 18);

  std::unordered_map<int, int> map;
  map[10] = 100;
  map[5] = 50;
  map[15] = 150;
  map[12] = 120;
  map[18] = 180;

  std::vector<int> bst_vals;
  inorder(root, bst_vals);

  int sum = 0;
  for (int v : bst_vals) {
    sum += map[v];
  }

  std::cout << sum << std::endl;
  return 0;
}

A 620

B 580

C 600

D Syntax error

💡 Hint

Add the values from the map in the order of BST in-order traversal.

The BST in-order traversal visits nodes in ascending order: 5, 10, 12, 15, 18. Summing their mapped values: 50 + 100 + 120 + 150 + 180 = 600.

Practice

1. Which data structure is best suited when you need to maintain elements in sorted order and perform fast range queries?

easy

A. Hash Map

B. Binary Search Tree (BST)

C. Stack

D. Queue

Solution

1. Step 1: Understand the need for sorted order

   Maintaining elements in sorted order requires a data structure that keeps elements arranged by key values.

2. Step 2: Identify data structure supporting range queries

   BST supports in-order traversal which gives sorted order and allows efficient range queries. Hash Map does not maintain order.

3. Final Answer:

   Binary Search Tree (BST) -> Option B

4. Quick Check:

   Sorted order + range queries = BST [OK]

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

Common Mistakes:

• Thinking hash maps keep elements sorted
• Confusing stack or queue with ordered data structures

2. Which of the following is the correct way to declare a hash map in C++ that maps integers to strings?

easy

A. unordered_map myMap;

B. std::map myMap;

C. std::unordered_map myMap;

D. hash_map myMap;

Solution

1. Step 1: Identify correct C++ hash map syntax

   The standard C++ hash map is declared using std::unordered_map with template parameters for key and value types.

2. Step 2: Check namespace and types

   std::unordered_map is correct. std::map is ordered map, not hash map. "hash_map" is non-standard. "unordered_map" without std:: is incomplete.

3. Final Answer:

   std::unordered_map myMap; -> Option C

4. Quick Check:

   Correct hash map syntax = std::unordered_map [OK]

Hint: Use std::unordered_map for hash map [OK]

Common Mistakes:

• Using std::map instead of unordered_map for hash map
• Omitting std:: namespace
• Using non-standard hash_map

3. Consider the following C++ code using a BST and a hash map:

std::map bst;
bst[3] = "three";
bst[1] = "one";
bst[2] = "two";

std::unordered_map hashMap;
hashMap[3] = "three";
hashMap[1] = "one";
hashMap[2] = "two";

for (auto &p : bst) std::cout << p.first << " ";
std::cout << std::endl;
for (auto &p : hashMap) std::cout << p.first << " ";

What is the output of this code?

medium

A. 3 2 1
3 2 1

B. 3 1 2
1 2 3

C. 1 2 3
1 2 3

D. 1 2 3
3 1 2

Solution

1. Step 1: Understand std::map iteration order

   std::map is a BST-based ordered map, iterates keys in ascending order: 1 2 3.

2. Step 2: Understand std::unordered_map iteration order

   std::unordered_map does not guarantee order; insertion order is not preserved. Output could be 3 1 2 or any order, but here likely 3 1 2 as inserted.

3. Final Answer:

   1 2 3 3 1 2 -> Option D

4. Quick Check:

   Ordered map prints sorted keys, hash map prints unordered keys [OK]

Hint: std::map prints sorted keys; unordered_map order is unpredictable [OK]

Common Mistakes:

• Assuming unordered_map prints keys sorted
• Confusing std::map and std::unordered_map iteration order

4. The following code attempts to use a BST and a hash map to store and print keys. Identify the error:

std::map bst;
bst[5] = "five";
bst[3] = "three";

std::unordered_map hashMap;
hashMap[5] = "five";
hashMap[3] = "three";

for (auto it = bst.begin(); it != bst.end(); ++it)
    std::cout << it->second << " ";

for (auto it = hashMap.begin(); it != hashMap.end(); ++it)
    std::cout << it->first << " ";

medium

A. Missing #include <unordered_map>

B. No error; code runs correctly

C. Using it->second in hashMap loop instead of it->first

D. Cannot use iterators with std::unordered_map

Solution

1. Step 1: Check code for missing includes

   std::unordered_map requires including <unordered_map> header. Without it, code will not compile.

2. Step 2: Verify iterator usage and member access

   Iterators and it->first/second usage are correct for both containers.

3. Final Answer:

   Missing #include <unordered_map> -> Option A

4. Quick Check:

   unordered_map needs #include <unordered_map> [OK]

Hint: Always include <unordered_map> for std::unordered_map [OK]

Common Mistakes:

• Assuming iterators can't be used with unordered_map
• Confusing it->first and it->second usage
• Ignoring missing header includes

5. You need to store a large dataset of user IDs (integers) with their scores (integers). You want to quickly find the top 10 users with the highest scores and also check if a user ID exists efficiently. Which data structure or combination is best suited?

hard

A. Use a BST keyed by score and a hash map for user ID lookup

B. Use only a hash map for all operations

C. Use a hash map for user ID to score and a max-heap for top scores

D. Use a BST keyed by user ID only

Solution

1. Step 1: Identify requirements

   Need fast user ID existence check and fast retrieval of top 10 users by score.

2. Step 2: Analyze data structure trade-offs

   Hash map gives O(1) user ID lookup but no order. BST keyed by score allows ordered traversal for top scores. Combining BST keyed by score and hash map keyed by user ID allows both operations efficiently.

3. Final Answer:

   Use a BST keyed by score and a hash map for user ID lookup -> Option A

4. Quick Check:

   Top scores + fast ID check = BST + hash map combo [OK]

Hint: Combine BST (score) + hash map (ID) for order and fast lookup [OK]

Common Mistakes:

• Using only hash map loses order for top scores
• Using only BST keyed by ID can't get top scores easily
• Ignoring need for two data structures