BST vs Hash Map Trade-offs for Ordered Data in DSA Rust - 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 want to see the contacts in alphabetical order sometimes, and also quickly find a contact by name.

🎯 Goal: Build a Rust program that stores contacts in a BTreeMap (a type of binary search tree) and a HashMap. You will add contacts, then print them in order from the BTreeMap, and also quickly look up a contact's phone number using the HashMap.

📋 What You'll Learn

Create a BTreeMap called contacts_btree with given contacts

Create a HashMap called contacts_hash with the same contacts

Use a variable search_name to hold the name to look up

Use a for loop to print all contacts from contacts_btree in alphabetical order

Look up search_name in contacts_hash and print the phone number

💡 Why This Matters

🌍 Real World

Many apps need to store data that can be quickly searched and sometimes shown in order, like contact lists, product catalogs, or leaderboards.

💼 Career

Understanding when to use ordered maps like <code>BTreeMap</code> versus unordered maps like <code>HashMap</code> is important for writing efficient and correct software.

1

Create the BTreeMap with contacts

Create a BTreeMap called contacts_btree and insert these entries exactly: ("Alice", "555-1234"), ("Bob", "555-5678"), ("Charlie", "555-8765").

DSA Rust

use std::collections::BTreeMap;

// Create contacts_btree and insert contacts
// Your code here

Hint

Use BTreeMap::new() to create the map, then insert to add each contact.

2

Create the HashMap with the same contacts and add search_name

Add use std::collections::HashMap; at the top. Create a HashMap called contacts_hash and insert the same contacts as in contacts_btree. Then create a variable search_name and set it to "Bob".

DSA Rust

use std::collections::BTreeMap;
use std::collections::HashMap;

fn main() {
    let mut contacts_btree = BTreeMap::new();
    contacts_btree.insert("Alice", "555-1234");
    contacts_btree.insert("Bob", "555-5678");
    contacts_btree.insert("Charlie", "555-8765");

    // Create contacts_hash and insert contacts
    // Create search_name variable
    // Your code here
}

Hint

Use HashMap::new() and insert like with BTreeMap. Set search_name to "Bob".

3

Print all contacts from BTreeMap in alphabetical order

Use a for loop with variables name and phone to iterate over contacts_btree.iter(). Inside the loop, print each contact in the format: "{name}: {phone}".

DSA Rust

use std::collections::BTreeMap;
use std::collections::HashMap;

fn main() {
    let mut contacts_btree = BTreeMap::new();
    contacts_btree.insert("Alice", "555-1234");
    contacts_btree.insert("Bob", "555-5678");
    contacts_btree.insert("Charlie", "555-8765");

    let mut contacts_hash = HashMap::new();
    contacts_hash.insert("Alice", "555-1234");
    contacts_hash.insert("Bob", "555-5678");
    contacts_hash.insert("Charlie", "555-8765");

    let search_name = "Bob";

    // Use for loop to print contacts_btree
    // Your code here
}

Hint

Use for (name, phone) in contacts_btree.iter() and println!("{}: {}", name, phone).

4

Look up search_name in HashMap and print the phone number

Use contacts_hash.get(search_name) to find the phone number. If found, print "Found {search_name}: {phone}". If not found, print "{search_name} not found".

DSA Rust

use std::collections::BTreeMap;
use std::collections::HashMap;

fn main() {
    let mut contacts_btree = BTreeMap::new();
    contacts_btree.insert("Alice", "555-1234");
    contacts_btree.insert("Bob", "555-5678");
    contacts_btree.insert("Charlie", "555-8765");

    let mut contacts_hash = HashMap::new();
    contacts_hash.insert("Alice", "555-1234");
    contacts_hash.insert("Bob", "555-5678");
    contacts_hash.insert("Charlie", "555-8765");

    let search_name = "Bob";

    for (name, phone) in contacts_btree.iter() {
        println!("{}: {}", name, phone);
    }

    // Use get() on contacts_hash to find search_name
    // Print found or not found message
    // Your code here
}

Hint

Use match contacts_hash.get(search_name) to check if the phone number exists and print accordingly.

Practice

1. Which data structure is best suited when you need to maintain elements in sorted order and perform fast range queries?

easy

A. Stack

B. Hash Map

C. Binary Search Tree (BST)

D. Queue

Solution

1. Step 1: Understand the need for sorted order

   Maintaining sorted order requires a data structure that keeps elements arranged by key value.

2. Step 2: Compare BST and Hash Map for sorted data

   BST keeps elements in sorted order naturally, allowing range queries. Hash Map does not maintain order.

3. Final Answer:

   Binary Search Tree (BST) -> Option C

4. Quick Check:

   Sorted order + range queries = BST [OK]

Hint: Sorted order needs BST, not Hash Map [OK]

Common Mistakes:

• Choosing Hash Map for ordered data
• Confusing Stack or Queue with sorted structures
• Ignoring range query requirements

2. Which Rust syntax correctly declares a HashMap with keys as integers and values as strings?

easy

A. let map = HashMap();

B. let map: HashMap = HashMap::new();

C. let map: HashMap = new HashMap();

D. let map = HashMap::new();

Solution

1. Step 1: Recall Rust HashMap declaration syntax

   Rust uses HashMap::new() to create a new map, with type annotation for key and value.

2. Step 2: Check each option for correct syntax

   let map: HashMap = HashMap::new(); uses correct syntax with type annotation and new() method. Others have syntax errors.

3. Final Answer:

   let map: HashMap = HashMap::new(); -> Option B

4. Quick Check:

   Rust HashMap declaration = let map: HashMap = HashMap::new(); [OK]

Hint: Use HashMap::new() with type annotation [OK]

Common Mistakes:

• Omitting type annotation
• Using parentheses instead of ::new()
• Incorrect generic syntax

3. Consider this Rust code using a BST-like structure for ordered keys:

let mut bst = BTreeMap::new();
bst.insert(3, "three");
bst.insert(1, "one");
bst.insert(2, "two");
for (key, value) in &bst {
    println!("{} -> {}", key, value);
}

What is the printed output order?

medium

A. 3 -> three
1 -> one
2 -> two

B. 2 -> two
3 -> three
1 -> one

C. Insertion order: 3 -> three
1 -> one
2 -> two

D. 1 -> one
2 -> two
3 -> three

Solution

1. Step 1: Understand BTreeMap ordering

   BTreeMap stores keys in sorted order, so iteration yields keys in ascending order.

2. Step 2: Trace insertion and iteration

   Keys inserted: 3, 1, 2. Iteration prints keys sorted: 1, 2, 3 with their values.

3. Final Answer:

   1 -> one 2 -> two 3 -> three -> Option D

4. Quick Check:

   BTreeMap iteration = sorted keys [OK]

Hint: BTreeMap iterates keys in sorted order [OK]

Common Mistakes:

• Assuming insertion order is preserved
• Confusing HashMap with BTreeMap
• Expecting reverse order

4. This Rust code tries to use a HashMap to get sorted keys:

let mut map = HashMap::new();
map.insert(10, "ten");
map.insert(5, "five");
map.insert(7, "seven");
for key in map.keys() {
    println!("{}", key);
}

What is the main problem with this code if the goal is to print keys in ascending order?

medium

A. HashMap keys() does not guarantee order

B. Keys are printed in reverse order

C. HashMap does not support integer keys

D. Code will cause a compile-time error

Solution

1. Step 1: Understand HashMap key ordering

   HashMap stores keys without any order; keys() returns keys in arbitrary order.

2. Step 2: Identify issue with printing keys

   Since keys() order is arbitrary, printing keys will not be sorted ascending.

3. Final Answer:

   HashMap keys() does not guarantee order -> Option A

4. Quick Check:

   HashMap unordered keys = HashMap keys() does not guarantee order [OK]

Hint: HashMap keys unordered, use BTreeMap for sorting [OK]

Common Mistakes:

• Expecting sorted output from HashMap
• Thinking keys() returns reverse order
• Assuming compile error due to key type

5. You need to store a large dataset with unique integer keys and values, and you want to perform fast lookups and also quickly find all keys within a range. Which data structure should you choose in Rust, and why?

hard

A. BTreeMap, because it keeps keys sorted and supports efficient range queries

B. HashMap, because it offers O(1) average lookup but no order for range queries

C. Vec, because it stores data contiguously and supports binary search

D. LinkedList, because it allows easy insertion and traversal

Solution

1. Step 1: Analyze lookup and range query needs

   Fast lookups and range queries require a data structure that supports both efficiently.

2. Step 2: Compare data structures for these needs

   HashMap offers fast lookups but no order for range queries. Vec supports binary search but slow insertions. LinkedList is slow for lookups. BTreeMap keeps keys sorted and supports efficient range queries.

3. Final Answer:

   BTreeMap, because it keeps keys sorted and supports efficient range queries -> Option A

4. Quick Check:

   Fast lookup + range queries = BTreeMap [OK]

Hint: Use BTreeMap for sorted keys and range queries [OK]

Common Mistakes:

• Choosing HashMap ignoring range queries
• Using Vec without considering insertion cost
• Selecting LinkedList for fast lookups