BST vs Hash Map Trade-offs for Ordered Data in DSA C - Build Both Approaches

BST vs Hash Map Trade-offs for Ordered Data

📖 Scenario: Imagine you are managing a small library system. You want to store book IDs and their titles. You need to quickly find a book by its ID, but sometimes you also want to list all books in order of their IDs.

🎯 Goal: You will create a simple data structure to store book IDs and titles. Then, you will compare how a Binary Search Tree (BST) and a Hash Map handle storing and retrieving ordered data.

📋 What You'll Learn

Create a BST node structure with book ID and title

Create a hash map array to store book titles by book ID

Insert three books with IDs 101, 50, and 150

Traverse the BST in order to print books sorted by ID

Print book titles from the hash map by their IDs

💡 Why This Matters

🌍 Real World

Libraries, databases, and many software systems need to store and retrieve data quickly and sometimes in order. Understanding BST and hash map trade-offs helps choose the right data structure.

💼 Career

Software developers often decide between trees and hash maps for tasks like indexing, caching, and searching. Knowing their strengths and weaknesses is key for efficient coding.

1

Create BST Node Structure and Insert Books

Define a struct called BSTNode with int id, char title[50], and pointers left and right. Then create three nodes with IDs 101, 50, and 150 and titles "Book A", "Book B", and "Book C" respectively. Link them to form a BST where 101 is root, 50 is left child, and 150 is right child.

DSA C

// Define BSTNode struct and create three nodes
// Your code here

Hint

Use typedef struct BSTNode to define the node. Use malloc to create nodes and strcpy to copy titles.

2

Create Hash Map Array for Book Titles

Create a char* array called hashMap of size 200 initialized to NULL. Then assign hashMap[101] to "Book A", hashMap[50] to "Book B", and hashMap[150] to "Book C".

DSA C

#include 
#include 
#include 

typedef struct BSTNode {
    int id;
    char title[50];
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

int main() {
    BSTNode* root = (BSTNode*)malloc(sizeof(BSTNode));
    root->id = 101;
    strcpy(root->title, "Book A");
    root->left = (BSTNode*)malloc(sizeof(BSTNode));
    root->left->id = 50;
    strcpy(root->left->title, "Book B");
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (BSTNode*)malloc(sizeof(BSTNode));
    root->right->id = 150;
    strcpy(root->right->title, "Book C");
    root->right->left = NULL;
    root->right->right = NULL;

    // Create hashMap array and assign titles
    // Your code here

    return 0;
}

Hint

Declare char* hashMap[200] and initialize all to NULL. Then assign titles to the correct indices.

3

Traverse BST In-Order to Print Books Sorted by ID

Write a recursive function void inorder(BSTNode* root) that prints each node's id and title in ascending order by traversing left child, then root, then right child. Call inorder(root) in main.

DSA C

#include 
#include 
#include 

typedef struct BSTNode {
    int id;
    char title[50];
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

// Write inorder function here

int main() {
    BSTNode* root = (BSTNode*)malloc(sizeof(BSTNode));
    root->id = 101;
    strcpy(root->title, "Book A");
    root->left = (BSTNode*)malloc(sizeof(BSTNode));
    root->left->id = 50;
    strcpy(root->left->title, "Book B");
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (BSTNode*)malloc(sizeof(BSTNode));
    root->right->id = 150;
    strcpy(root->right->title, "Book C");
    root->right->left = NULL;
    root->right->right = NULL;

    char* hashMap[200] = {NULL};
    hashMap[101] = "Book A";
    hashMap[50] = "Book B";
    hashMap[150] = "Book C";

    // Call inorder function here
    // Your code here

    return 0;
}

Hint

Use recursion to visit left child, print current node, then right child.

4

Print Book Titles from Hash Map by IDs

Print the titles stored in hashMap at indices 50, 101, and 150 using printf. Print each title on a new line.

DSA C

#include 
#include 
#include 

typedef struct BSTNode {
    int id;
    char title[50];
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

void inorder(BSTNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d: %s\n", root->id, root->title);
    inorder(root->right);
}

int main() {
    BSTNode* root = (BSTNode*)malloc(sizeof(BSTNode));
    root->id = 101;
    strcpy(root->title, "Book A");
    root->left = (BSTNode*)malloc(sizeof(BSTNode));
    root->left->id = 50;
    strcpy(root->left->title, "Book B");
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (BSTNode*)malloc(sizeof(BSTNode));
    root->right->id = 150;
    strcpy(root->right->title, "Book C");
    root->right->left = NULL;
    root->right->right = NULL;

    char* hashMap[200] = {NULL};
    hashMap[101] = "Book A";
    hashMap[50] = "Book B";
    hashMap[150] = "Book C";

    inorder(root);

    // Print titles from hashMap
    // Your code here

    return 0;
}

Hint

Use printf("%s\n", hashMap[50]) and similarly for other IDs.

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