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.