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

Mental Model

A BST keeps data sorted and lets you find items in order, while a hash map finds items fast but doesn't keep order.

Analogy: Think of a phone book (BST) where names are in order so you can flip through alphabetically, versus a big box of cards (hash map) where you find a card quickly by looking up a label but the cards are all mixed up.

BST:
    5
   / \
  3   7
 /     \
2       9

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

Dry Run Walkthrough

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

Goal: Show how BST keeps keys sorted and hash map finds key fast but unordered

Step 1: Insert 5 into empty BST and hash map

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

Why: Start with first key in both structures

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

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

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

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

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

Why: BST places larger key right; hash map adds new entry

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

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

Why: BST keeps smaller keys further left; hash map stores by hash

Step 5: Insert 9 into BST right of 7; insert in hash map at hash(9)

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

Why: BST keeps larger keys further right; hash map stores by hash

Step 6: Search for key 7 in BST by comparing and moving right

BST traversal: 5 -> 7 found
Hash Map lookup: direct at [hash(7)]

Why: BST search follows order; hash map finds directly by hash

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

class BST {
public:
    Node* root;
    BST() : root(nullptr) {}

    void insert(int key) {
        root = insertRec(root, key);
    }

    Node* insertRec(Node* node, int key) {
        if (!node) return new Node(key); // create new node if null
        if (key < node->key) node->left = insertRec(node->left, key); // go left if smaller
        else if (key > node->key) node->right = insertRec(node->right, key); // go right if larger
        return node; // return unchanged node pointer
    }

    bool search(int key) {
        Node* curr = root;
        while (curr) {
            if (key == curr->key) return true; // found key
            else if (key < curr->key) curr = curr->left; // go left
            else curr = curr->right; // go right
        }
        return false; // not found
    }

    void inorderPrint(Node* node) {
        if (!node) return;
        inorderPrint(node->left);
        cout << node->key << " ";
        inorderPrint(node->right);
    }
};

int main() {
    BST bst;
    unordered_map<int, string> hashmap;

    int keys[] = {5, 3, 7, 2, 9};
    for (int k : keys) {
        bst.insert(k); // insert in BST
        hashmap[k] = "val"; // insert in hash map
    }

    cout << "BST inorder: ";
    bst.inorderPrint(bst.root);
    cout << "\n";

    int searchKey = 7;
    cout << "BST search for " << searchKey << ": " << (bst.search(searchKey) ? "found" : "not found") << "\n";

    cout << "Hash map search for " << searchKey << ": ";
    if (hashmap.find(searchKey) != hashmap.end()) cout << "found";
    else cout << "not found";
    cout << "\n";

    return 0;
}

if (!node) return new Node(key);

create new node when reaching null position in BST

if (key < node->key) node->left = insertRec(node->left, key);

go left if key smaller to keep BST order

else if (key > node->key) node->right = insertRec(node->right, key);

go right if key larger to keep BST order

while (curr) { if (key == curr->key) return true; else if (key < curr->key) curr = curr->left; else curr = curr->right; }

search BST by comparing and moving left or right

hashmap[k] = "val";

insert key-value pair in hash map for O(1) access

if (hashmap.find(searchKey) != hashmap.end()) cout << "found";

directly check presence in hash map

Output

BST inorder: 2 3 5 7 9 

BST search for 7: found

Hash map search for 7: found

Complexity Analysis

Time: O(log n) average for BST operations because it traverses height; O(1) average for hash map lookup due to direct indexing

Space: O(n) for both BST and hash map because they store all keys

vs Alternative: BST keeps keys sorted for ordered traversal but slower search; hash map is faster for search but unordered

Edge Cases

Empty BST and hash map

Search returns not found; insert creates first node or entry

DSA C++

if (!node) return new Node(key);

Duplicate keys insertion

BST ignores duplicates by not inserting again; hash map overwrites value

DSA C++

else if (key > node->key) node->right = insertRec(node->right, key);

Searching for non-existent key

BST search returns false after reaching null; hash map returns not found

DSA C++

while (curr) { ... } return false;

When to Use This Pattern

When a problem needs both fast search and ordered data access, consider BST for order and hash map for speed; trade-offs depend on whether order or speed is priority.

Common Mistakes

Mistake: Assuming hash map keeps keys in order
Fix: Remember hash maps do not maintain order; use BST or balanced tree for ordered data

Mistake: Not handling duplicates in BST insert causing infinite recursion
Fix: Add condition to ignore or handle duplicates explicitly

Summary

BST stores keys in sorted order allowing ordered traversal and search in O(log n) average time.

Use BST when you need to keep data sorted and perform range queries or ordered operations.

The key insight is BST maintains order by placing smaller keys left and larger keys right, unlike hash maps which are unordered but faster for direct lookup.

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