BST vs Hash Map Trade-offs for Ordered Data in DSA Go - Key Differences

Recall & Review

beginner

What is a key advantage of a Binary Search Tree (BST) over a Hash Map when working with ordered data?

A BST maintains elements in sorted order, allowing efficient in-order traversal to access data in ascending or descending order.

intermediate

Why might a Hash Map be less suitable than a BST for range queries?

Hash Maps do not maintain any order, so range queries require checking all keys, making them inefficient compared to BSTs which can quickly navigate ranges.

intermediate

In terms of average time complexity, how do BSTs and Hash Maps compare for search operations?

Hash Maps offer average O(1) search time, while BSTs offer O(log n) if balanced; however, BSTs provide ordered data access which Hash Maps do not.

intermediate

What is a potential downside of using a BST compared to a Hash Map?

BSTs can become unbalanced, leading to O(n) worst-case search time, while Hash Maps maintain consistent average O(1) search time regardless of data order.

advanced

How does memory usage typically compare between BSTs and Hash Maps?

Hash Maps often use more memory due to storing keys, values, and handling collisions, while BSTs store nodes with pointers but usually have less overhead.

Which data structure is best suited for retrieving data in sorted order?

A Hash Map

B Queue

C Stack

D Binary Search Tree

Binary Search Trees keep data sorted, enabling ordered retrieval.

What is the average time complexity of search in a Hash Map?

A O(1)

B O(n)

C O(log n)

D O(n log n)

Hash Maps provide average constant time O(1) search.

Why might a BST perform worse than a Hash Map in some cases?

A BSTs do not store keys

B BSTs use more memory

C BSTs can become unbalanced causing O(n) search time

D BSTs cannot store duplicate values

Unbalanced BSTs degrade to linear search time.

Which data structure is more efficient for range queries?

A Binary Search Tree

B Linked List

C Hash Map

D Array

BSTs allow efficient range queries due to ordered structure.

Which data structure typically uses more memory due to collision handling?

A Binary Search Tree

B Hash Map

C Heap

D Graph

Hash Maps use extra memory for buckets and collision resolution.

Explain the trade-offs between using a Binary Search Tree and a Hash Map for storing ordered data.

Think about order, speed, and memory.

Describe scenarios where a BST is preferred over a Hash Map and vice versa.

Consider what you need: order or speed.

Practice

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

easy

A. Hash Map

B. Binary Search Tree (BST)

C. Stack

D. Queue

Solution

1. Step 1: Understand the requirement for sorted order

   Maintaining sorted order means elements must be kept in a sequence where each element is greater or smaller than its neighbors.

2. Step 2: Identify data structure supporting range queries

   BSTs keep elements sorted and allow efficient range queries, while hash maps do 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 Go that maps strings to integers?

easy

A. var m map[string]int = map[string]int

B. var m map[int]string = make(map[string]int)

C. var m map[string]int = make(map[string]int)

D. var m map[string]int = new(map[string]int)

Solution

1. Step 1: Understand Go map declaration syntax

   In Go, maps are declared with 'make' to allocate memory, e.g., make(map[keyType]valueType).

2. Step 2: Check each option for correctness

   var m map[string]int = make(map[string]int) correctly declares and initializes a map from string to int. var m map[int]string = make(map[string]int) has mismatched types. var m map[string]int = new(map[string]int) uses 'new' which returns a pointer, not a map. var m map[string]int = map[string]int declares but does not initialize the map properly.

3. Final Answer:

   var m map[string]int = make(map[string]int) -> Option C

4. Quick Check:

   Use make() to initialize maps in Go [OK]

Hint: Use make() to initialize maps, not new() [OK]

Common Mistakes:

• Using new() instead of make() for maps
• Mismatching key and value types
• Declaring map without initialization

3. Consider the following Go code using a BST and a hash map. What will be the output?

package main
import "fmt"
type Node struct {
    val   int
    left  *Node
    right *Node
}
func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val < root.val {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}
func inorder(root *Node) {
    if root != nil {
        inorder(root.left)
        fmt.Print(root.val, " ")
        inorder(root.right)
    }
}
func main() {
    root := (*Node)(nil)
    values := []int{5, 3, 7, 2, 4}
    for _, v := range values {
        root = insert(root, v)
    }
    inorder(root)
    fmt.Println()
    m := make(map[int]string)
    m[5] = "five"
    m[3] = "three"
    m[7] = "seven"
    fmt.Println(m[3])
}

medium

A. 2 3 4 5 7
three

B. 5 3 7 2 4
three

C. 2 3 4 5 7
five

D. 3 4 2 5 7
seven

Solution

1. Step 1: Trace BST insertion and inorder traversal

   Inserting 5,3,7,2,4 into BST and then inorder traversal prints sorted order: 2 3 4 5 7.

2. Step 2: Check hash map access

   Map m has key 3 with value "three", so printing m[3] outputs "three".

3. Final Answer:

   2 3 4 5 7 three -> Option A

4. Quick Check:

   BST inorder = sorted; map lookup by key = value [OK]

Hint: BST inorder prints sorted; map key lookup returns stored value [OK]

Common Mistakes:

• Assuming map keys print in order
• Confusing preorder with inorder traversal
• Mixing up map values for keys

4. The following Go code attempts to use a hash map to store integer keys and string values. It has a bug. What is the bug?

package main
import "fmt"
func main() {
    var m map[int]string
    m[1] = "one"
    fmt.Println(m[1])
}

medium

A. Map m is declared but not initialized, causing a runtime panic

B. Key type int is invalid for maps in Go

C. String values cannot be stored in maps

D. fmt.Println cannot print map values directly

Solution

1. Step 1: Analyze map declaration and initialization

   The map m is declared but not initialized with make(), so it is nil.

2. Step 2: Understand consequences of nil map assignment

   Assigning to a nil map causes a runtime panic: assignment to entry in nil map.

3. Final Answer:

   Map m is declared but not initialized, causing a runtime panic -> Option A

4. Quick Check:

   Maps must be initialized with make() before assignment [OK]

Hint: Always initialize maps with make() before adding entries [OK]

Common Mistakes:

• Assuming declaration alone creates usable map
• Thinking key types are restricted to strings
• Believing fmt.Println can't print map values

5. You need to store a large dataset of user IDs (integers) with their last login timestamps and frequently perform these operations: fast lookup by user ID, and queries to find all users who logged in within a certain time range. Which data structure combination is best to optimize both operations?

hard

A. Use a queue to store user IDs and timestamps in order

B. Use only a hash map keyed by user ID storing timestamps

C. Use only a BST keyed by user ID storing timestamps

D. Use a hash map for user ID to timestamp, and a balanced BST keyed by timestamp for range queries

Solution

1. Step 1: Identify requirements for fast lookup and range queries

   Fast lookup by user ID suggests hash map keyed by user ID. Range queries by timestamp suggest BST keyed by timestamp.

2. Step 2: Combine data structures to optimize both operations

   Using both a hash map (for O(1) lookup) and a balanced BST (for ordered range queries) meets both needs efficiently.

3. Final Answer:

   Use a hash map for user ID to timestamp, and a balanced BST keyed by timestamp for range queries -> Option D

4. Quick Check:

   Hash map + BST combo optimizes lookup and range queries [OK]

Hint: Combine hash map for lookup and BST for ordered range queries [OK]

Common Mistakes:

• Using only one data structure and missing efficiency
• Using queue which doesn't support fast lookup or range queries
• Confusing keys for lookup and range queries