BST vs Hash Map Trade-offs for Ordered Data in DSA C - Trade-offs & Analysis

Mental Model

A Binary Search Tree (BST) keeps data sorted and allows ordered operations, while a Hash Map stores data for fast lookup but does not keep order.

Analogy: Think of a BST like a sorted bookshelf where you can find books in order and add new ones in the right place. A Hash Map is like a labeled box where you quickly find a book by its label but the books inside are not sorted.

BST:
     5
    / \
   3   7
  /     \
 2       8

Hash Map:
[0]: null
[1]: (key=3, val)
[2]: (key=5, val)
[3]: (key=7, val)
[4]: null

Dry Run Walkthrough

Input: Insert keys 5, 3, 7, 2, 8 and then search for key 7

Goal: Show how BST keeps keys ordered and allows searching in order, while Hash Map finds key quickly but order is lost

Step 1: Insert 5 into empty BST and Hash Map

BST: 5 -> null
Hash Map: [hash(5)]: (5) -> null

Why: Start with first key in both structures

Step 2: Insert 3 into BST left of 5; insert into Hash Map at hash(3)

BST: 5 -> left -> 3 -> null
Hash Map: [hash(3)]: (3) -> null, [hash(5)]: (5) -> null

Why: BST keeps order by placing smaller key left; Hash Map stores by hash

Step 3: Insert 7 into BST right of 5; insert into Hash Map at hash(7)

BST: 5 -> left -> 3, right -> 7 -> null
Hash Map: [hash(3)]: (3), [hash(5)]: (5), [hash(7)]: (7)

Why: BST places larger key right; Hash Map stores by hash

Step 4: Insert 2 into BST left of 3; insert into Hash Map at hash(2)

BST: 5 -> 3 -> 2 (left)
Hash Map: keys at hash(2), hash(3), hash(5), hash(7)

Why: BST maintains order by placing smaller keys left; Hash Map stores by hash

Step 5: Insert 8 into BST right of 7; insert into Hash Map at hash(8)

BST: 5 -> 3 -> 2 (left), 7 -> 8 (right)
Hash Map: keys at hash(2), hash(3), hash(5), hash(7), hash(8)

Why: BST keeps sorted order; Hash Map stores keys by hash

Step 6: Search for key 7 in BST by comparing from root

BST traversal: 5 -> 7 found
Hash Map: direct access at hash(7)

Why: BST search follows tree path; Hash Map uses direct hash lookup

Result:

BST final: 5 -> 3 -> 2 (left), 7 -> 8 (right)
Hash Map final: keys stored at hash indices (unordered)
Search result: key 7 found in both

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// BST Node
typedef struct BSTNode {
    int key;
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

// Create new BST node
BSTNode* newBSTNode(int key) {
    BSTNode* node = (BSTNode*)malloc(sizeof(BSTNode));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Insert key into BST
BSTNode* bstInsert(BSTNode* root, int key) {
    if (root == NULL) return newBSTNode(key); // insert at leaf
    if (key < root->key) root->left = bstInsert(root->left, key); // go left
    else if (key > root->key) root->right = bstInsert(root->right, key); // go right
    return root; // unchanged if duplicate
}

// Search key in BST
int bstSearch(BSTNode* root, int key) {
    if (root == NULL) return 0; // not found
    if (key == root->key) return 1; // found
    if (key < root->key) return bstSearch(root->left, key); // search left
    else return bstSearch(root->right, key); // search right
}

// Hash Map with simple chaining
#define TABLE_SIZE 10

typedef struct HashNode {
    int key;
    struct HashNode* next;
} HashNode;

HashNode* hashTable[TABLE_SIZE];

// Simple hash function
int hash(int key) {
    return key % TABLE_SIZE;
}

// Insert key into Hash Map
void hashInsert(int key) {
    int idx = hash(key);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->next = hashTable[idx]; // insert at head
    hashTable[idx] = newNode;
}

// Search key in Hash Map
int hashSearch(int key) {
    int idx = hash(key);
    HashNode* curr = hashTable[idx];
    while (curr != NULL) {
        if (curr->key == key) return 1; // found
        curr = curr->next; // check next in chain
    }
    return 0; // not found
}

// Print BST inorder (sorted)
void printBST(BSTNode* root) {
    if (root == NULL) return;
    printBST(root->left);
    printf("%d ", root->key);
    printBST(root->right);
}

// Print Hash Map contents
void printHashMap() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("[%d]:", i);
        HashNode* curr = hashTable[i];
        while (curr != NULL) {
            printf(" %d ->", curr->key);
            curr = curr->next;
        }
        printf(" null\n");
    }
}

int main() {
    BSTNode* bstRoot = NULL;
    int keys[] = {5, 3, 7, 2, 8};
    int n = sizeof(keys)/sizeof(keys[0]);

    // Initialize hashTable to NULL
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }

    // Insert keys
    for (int i = 0; i < n; i++) {
        bstRoot = bstInsert(bstRoot, keys[i]);
        hashInsert(keys[i]);
    }

    // Print BST inorder
    printf("BST inorder: ");
    printBST(bstRoot);
    printf("\n");

    // Print Hash Map
    printf("Hash Map contents:\n");
    printHashMap();

    // Search for key 7
    int searchKey = 7;
    printf("Search key %d in BST: %s\n", searchKey, bstSearch(bstRoot, searchKey) ? "Found" : "Not Found");
    printf("Search key %d in Hash Map: %s\n", searchKey, hashSearch(searchKey) ? "Found" : "Not Found");

    return 0;
}

if (root == NULL) return newBSTNode(key);

insert new node at leaf position in BST

if (key < root->key) root->left = bstInsert(root->left, key);

go left if key smaller to keep BST order

else if (key > root->key) root->right = bstInsert(root->right, key);

go right if key larger to keep BST order

if (key == root->key) return 1;

found key in BST

int idx = hash(key);

compute hash index for key

newNode->next = hashTable[idx]; hashTable[idx] = newNode;

insert new node at head of chain in hash bucket

while (curr != NULL) { if (curr->key == key) return 1; curr = curr->next; }

search chain in hash bucket for key

Output

BST inorder: 2 3 5 7 8 

Hash Map contents:

[0]: null

[1]: 7 -> null

[2]: 2 -> null

[3]: 3 -> null

[4]: null

[5]: 5 -> null

[6]: null

[7]: null

[8]: 8 -> null

[9]: null

Search key 7 in BST: Found

Search key 7 in Hash Map: Found

Complexity Analysis

Time: BST operations are O(h) where h is tree height, average O(log n), worst O(n) if unbalanced; Hash Map operations are average O(1) but worst O(n) if many collisions

Space: Both use O(n) space to store n keys; BST nodes have pointers increasing overhead, Hash Map uses array plus linked lists

vs Alternative: BST supports ordered operations like range queries efficiently, Hash Map does not keep order but offers faster average lookup

Edge Cases

Empty BST and Hash Map

Insertions create first nodes; searches return not found

DSA C

if (root == NULL) return newBSTNode(key);

Duplicate keys insertion

BST ignores duplicates; Hash Map inserts duplicates in chain

DSA C

return root; // unchanged if duplicate

Hash collisions

Keys with same hash stored in linked list chain

DSA C

newNode->next = hashTable[idx]; hashTable[idx] = newNode;

When to Use This Pattern

When you need fast lookup plus ordered data access, consider BST for order and Hash Map for speed; knowing their trade-offs helps pick the right structure.

Common Mistakes

Mistake: Assuming Hash Map keeps keys sorted
Fix: Remember Hash Map stores keys unordered; use BST or balanced tree for order

Mistake: Ignoring BST unbalanced worst case
Fix: Consider balanced BST variants or Hash Map if worst-case performance matters

Summary

BST keeps data sorted and supports ordered operations; Hash Map offers fast average lookup without order.

Use BST when you need ordered data access or range queries; use Hash Map for fast key-value lookup without order.

The key insight is BST maintains order via tree structure, while Hash Map uses hashing for speed but loses order.

Practice

1. Which data structure is best suited for maintaining data in sorted order with efficient range queries?

easy

A. Hash Map

B. Stack

C. Binary Search Tree (BST)

D. Queue

Solution

1. Step 1: Understand data ordering requirements

   Range queries and sorted data require maintaining order among elements.

2. Step 2: Compare BST and Hash Map for ordering

   BST keeps elements in sorted order by design; Hash Map does not maintain order.

3. Final Answer:

   Binary Search Tree (BST) -> Option C

4. Quick Check:

   Ordered data = BST [OK]

Hint: For sorted data and range queries, choose BST [OK]

Common Mistakes:

• Thinking hash maps maintain order
• Confusing stack or queue as ordered structures
• Ignoring the need for range queries

2. Which of the following is the correct way to declare a hash map in C using standard libraries?

easy

A. #include \nhash_map map;

B. #include \nstruct hashmap map;

C. #include \nint map[100];

D. #include \nGHashTable *map = g_hash_table_new(g_int_hash, g_int_equal);

Solution

1. Step 1: Identify standard C hash map usage

   C standard library does not have built-in hash maps; GLib provides GHashTable.

2. Step 2: Check options for valid syntax

   #include <glib.h>\nGHashTable *map = g_hash_table_new(g_int_hash, g_int_equal); uses GLib's GHashTable correctly; others are invalid or incomplete.

3. Final Answer:

   #include <glib.h>\nGHashTable *map = g_hash_table_new(g_int_hash, g_int_equal); -> Option D

4. Quick Check:

   GLib hash map syntax = #include <glib.h>\nGHashTable *map = g_hash_table_new(g_int_hash, g_int_equal); [OK]

Hint: Use GLib for hash maps in C, not standard library [OK]

Common Mistakes:

• Assuming C has built-in hash map
• Using C++ syntax in C code
• Confusing arrays with hash maps

3. Consider the following code snippet using a BST and a hash map for storing integer keys. What will be the output of the in-order traversal of the BST after inserting keys 5, 3, 7, 2, 4?

medium

A. 2 -> 3 -> 4 -> 5 -> 7 -> null

B. 5 -> 3 -> 7 -> 2 -> 4 -> null

C. 7 -> 5 -> 4 -> 3 -> 2 -> null

D. 3 -> 2 -> 4 -> 5 -> 7 -> null

Solution

1. Step 1: Insert keys into BST

   Insert 5 as root, then 3 left of 5, 7 right of 5, 2 left of 3, 4 right of 3.

2. Step 2: Perform in-order traversal

   In-order visits left subtree, root, right subtree: 2, 3, 4, 5, 7.

3. Final Answer:

   2 -> 3 -> 4 -> 5 -> 7 -> null -> Option A

4. Quick Check:

   In-order BST traversal = sorted keys [OK]

Hint: In-order traversal of BST gives sorted keys [OK]

Common Mistakes:

• Confusing insertion order with traversal order
• Mixing pre-order or post-order traversal
• Assuming hash map order applies to BST

4. The following C code attempts to insert keys into a BST but causes a runtime error. What is the main issue?

typedef struct Node {
  int key;
  struct Node *left, *right;
} Node;

Node* insert(Node* root, int key) {
  if (root == NULL) {
    Node* newNode = malloc(sizeof(Node));
    newNode->key = key;
    return newNode;
  }
  if (key < root->key)
    root->left = insert(root->left, key);
  else
    root->right = insert(root->right, key);
  return root;
}

medium

A. newNode's left and right pointers are not initialized

B. malloc is not included via stdlib.h

C. The function does not handle duplicate keys

D. The root pointer is not updated in main

Solution

1. Step 1: Check new node initialization

   newNode's left and right pointers are not set, so they contain garbage values.

2. Step 2: Understand impact on BST

   Uninitialized pointers cause undefined behavior or runtime errors during traversal or further insertions.

3. Final Answer:

   newNode's left and right pointers are not initialized -> Option A

4. Quick Check:

   Initialize pointers to NULL to avoid errors [OK]

Hint: Always initialize new node pointers to NULL [OK]

Common Mistakes:

• Ignoring pointer initialization
• Assuming malloc auto-initializes memory
• Confusing duplicate key handling with runtime error

5. You need to store a large dataset of user IDs with associated scores. You want to quickly find users with scores in a specific range and also retrieve scores by user ID efficiently. Which combination of data structures is best?

hard

A. Use only a hash map keyed by user ID

B. Use a hash map for user ID to score and a balanced BST keyed by score for range queries

C. Use only a BST keyed by user ID

D. Use an array sorted by user ID

Solution

1. Step 1: Identify requirements

   Fast lookup by user ID and efficient range queries by score are needed.

2. Step 2: Match data structures to needs

   Hash map gives O(1) user ID lookup; balanced BST keyed by score supports range queries efficiently.

3. Step 3: Combine for best performance

   Using both structures together meets both requirements effectively.

4. Final Answer:

   Use a hash map for user ID to score and a balanced BST keyed by score for range queries -> Option B

5. Quick Check:

   Hash map + BST combo = best for lookup + range [OK]

Hint: Combine hash map for lookup and BST for range queries [OK]

Common Mistakes:

• Using only one structure and missing efficiency
• Using array which is slow for lookups
• Ignoring need for range queries