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: You are building a simple contact list app. You want to store contacts with their phone numbers. You need to quickly find a contact's number by name. Also, you want to see contacts in alphabetical order sometimes.

🎯 Goal: Build a program that stores contacts in a dictionary-like structure, then extracts and prints contacts in alphabetical order using a binary search tree (BST) approach.

📋 What You'll Learn

Create a dictionary called contacts with exact entries: "Alice": "1234", "Bob": "5678", "Charlie": "91011"

Create an empty binary search tree structure called bst to store contact names

Insert all contact names from contacts into bst in alphabetical order

Print the contact names in alphabetical order from bst

💡 Why This Matters

🌍 Real World

Contact lists, phone books, and any app needing fast lookup plus ordered display use these data structures.

💼 Career

Understanding when to use hash maps or BSTs helps in software engineering roles involving data storage, search optimization, and UI display.

1

Create the contacts dictionary

Create a dictionary called contacts with these exact entries: "Alice": "1234", "Bob": "5678", "Charlie": "91011"

DSA C++

# Create the contacts dictionary with exact entries
# Your code here

Hint

Use std::unordered_map<std::string, std::string> to create the dictionary with exact key-value pairs.

2

Create an empty BST structure

Create a struct called Node with std::string name, and pointers left and right. Then create a pointer called bst and set it to nullptr.

DSA C++

std::unordered_map contacts = {
    {"Alice", "1234"},
    {"Bob", "5678"},
    {"Charlie", "91011"}
};

// Define Node struct and create bst pointer
# Your code here

Hint

Define a struct with name and two child pointers. Initialize bst as a null pointer.

3

Insert contact names into BST

Write a function Node* insert(Node* root, std::string name) that inserts name into the BST rooted at root in alphabetical order. Then, use a for loop with auto& pair : contacts to insert each contact name into bst.

DSA C++

std::unordered_map contacts = {
    {"Alice", "1234"},
    {"Bob", "5678"},
    {"Charlie", "91011"}
};

struct Node {
    std::string name;
    Node* left;
    Node* right;
    Node(std::string n) : name(n), left(nullptr), right(nullptr) {}
};

Node* bst = nullptr;

// Write insert function and insert all names into bst
# Your code here

Hint

Use recursion to insert names alphabetically. Loop over contacts to insert each name.

4

Print contact names in alphabetical order

Write a function void inorderPrint(Node* root) that prints contact names in alphabetical order by traversing the BST in order. Then call inorderPrint(bst).

DSA C++

std::unordered_map contacts = {
    {"Alice", "1234"},
    {"Bob", "5678"},
    {"Charlie", "91011"}
};

struct Node {
    std::string name;
    Node* left;
    Node* right;
    Node(std::string n) : name(n), left(nullptr), right(nullptr) {}
};

Node* bst = nullptr;

Node* insert(Node* root, std::string name) {
    if (root == nullptr) {
        return new Node(name);
    }
    if (name name) {
        root->left = insert(root->left, name);
    } else if (name > root->name) {
        root->right = insert(root->right, name);
    }
    return root;
}

for (auto& pair : contacts) {
    bst = insert(bst, pair.first);
}

// Write inorderPrint function and call it
# Your code here

Hint

Use in-order traversal to print names alphabetically. Call inorderPrint(bst) inside main().