BST vs Hash Map Trade-offs for Ordered Data in DSA Go - Build Both Approaches

BST vs Hash Map Trade-offs for Ordered Data

📖 Scenario: Imagine you are building a simple contact list app. You want to store contacts with their phone numbers. Sometimes, you need to find a contact quickly by name. Other times, you want to list all contacts in alphabetical order.Two common ways to store this data are using a Binary Search Tree (BST) or a Hash Map. Each has its strengths and weaknesses.

🎯 Goal: Build a small program to store contacts using a map, then add a sorted list of contact names using a BST-like structure. This will help you see the difference in how data is stored and accessed.

📋 What You'll Learn

Create a map to store contact names and phone numbers.

Create a slice to hold contact names for sorting.

Sort the contact names alphabetically.

Print the contacts in alphabetical order.

💡 Why This Matters

🌍 Real World

Contact lists, phone books, and any app needing fast lookup and ordered display of data.

💼 Career

Understanding data structures like maps and trees helps in designing efficient software for search, sorting, and data management.

1

Create a map of contacts

Create a map called contacts with these exact entries: "Alice": "555-1234", "Bob": "555-5678", "Charlie": "555-8765"

DSA Go

# Create the map contacts with the given entries
# Your code here

Hint

Use map[string]string to create a map with string keys and string values.

2

Create a slice of contact names

Create a slice called names and add the keys from contacts to it using a for loop with variables name and phone iterating over contacts

DSA Go

package main

import "fmt"

func main() {
    contacts := map[string]string{
        "Alice": "555-1234",
        "Bob": "555-5678",
        "Charlie": "555-8765",
    }
    // Create a slice names and add contact names from contacts
    // Your code here
}

Hint

Use for name, phone := range contacts to loop over the map and append to add names to the slice.

3

Sort the contact names alphabetically

Import the sort package and use sort.Strings(names) to sort the names slice alphabetically

DSA Go

package main

import (
    "fmt"
    // Import sort package
)

func main() {
    contacts := map[string]string{
        "Alice": "555-1234",
        "Bob": "555-5678",
        "Charlie": "555-8765",
    }
    names := []string{}
    for name, phone := range contacts {
        _ = phone
        names = append(names, name)
    }
    // Sort the names slice alphabetically
    // Your code here
}

Hint

Use import "sort" and then call sort.Strings(names) to sort the slice.

4

Print contacts in alphabetical order

Use a for loop with variable _, name iterating over names and print each contact's name and phone number from contacts using fmt.Println(name, contacts[name])

DSA Go

package main

import (
    "fmt"
    "sort"
)

func main() {
    contacts := map[string]string{
        "Alice": "555-1234",
        "Bob": "555-5678",
        "Charlie": "555-8765",
    }
    names := []string{}
    for name, phone := range contacts {
        _ = phone
        names = append(names, name)
    }
    sort.Strings(names)
    // Print each contact name and phone number in alphabetical order
    // Your code here
}

Hint

Use for _, name := range names and print with fmt.Println(name, contacts[name]).

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