BST vs Hash Map Trade-offs for Ordered Data in DSA Rust - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a key-value pair into a binary search tree (BST).

DSA Rust

fn insert(root: &mut Option<Box<Node>>, key: i32, value: i32) {
    match root {
        None => *root = Some(Box::new(Node { key, value, left: None, right: None })),
        Some(ref mut node) => {
            if key < node.key {
                insert(&mut node.left, key, value);
            } else if key > node.key {
                insert(&mut node.right, key, value);
            } else {
                node.value = [1];
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

ANone

Bkey

Croot

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning the key instead of the value.

Trying to assign to root instead of node.value.

When the key already exists in the BST, we update the node's value with the new value provided.

2fill in blank

medium

Complete the code to check if a key exists in a hash map.

DSA Rust

fn contains_key(map: &std::collections::HashMap<i32, i32>, key: i32) -> bool {
    map.[1](&key)
}

Drag options to blanks, or click blank then click option'

Acontains_key

Bget

Cinsert

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using get which returns an Option instead of a boolean.

Using insert or remove which modify the map.

The method contains_key checks if the hash map has the given key.

3fill in blank

hard

Fix the error in the code to find the minimum key in a BST.

DSA Rust

fn find_min(root: &Option<Box<Node>>) -> Option<i32> {
    match root {
        None => None,
        Some(node) => {
            if node.left.is_none() {
                Some(node.[1])
            } else {
                find_min(&node.left)
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Akey

Bvalue

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Returning node.value instead of node.key.

Trying to access node.left or node.right instead of node.key.

The minimum key in a BST is found by going left until no left child exists, then returning the node's key.

4fill in blank

hard

Fill both blanks to create a hash map from a vector of key-value pairs and check if a key exists.

DSA Rust

let pairs = vec![(1, 10), (2, 20), (3, 30)];
let map: std::collections::HashMap<_, _> = pairs.[1]().collect();
let exists = map.[2](&2);

Drag options to blanks, or click blank then click option'

Ainto_iter

Bcontains_key

Citer

Dget

Attempts:

3 left

💡 Hint

Common Mistakes

Using iter instead of into_iter which borrows instead of consuming.

Using get which returns Option instead of boolean.

We convert the vector into an iterator with into_iter and then collect into a hash map. To check if key 2 exists, we use contains_key.

5fill in blank

hard

Fill all three blanks to create a BST from a vector, insert a new key-value pair, and find the minimum key.

DSA Rust

let mut root: Option<Box<Node>> = None;
for (k, v) in vec![(5, 50), (3, 30), (7, 70)] {
    insert(&mut root, k, v);
}
insert(&mut root, [1], [2]);
let min_key = find_min(&[3]);

Drag options to blanks, or click blank then click option'

A2

B20

Croot

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Using None instead of root for find_min.

Inserting a key already in the BST.

We insert key 2 with value 20 into the BST rooted at root, then find the minimum key starting from root.

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