BST vs Hash Map Trade-offs for Ordered Data in DSA Go - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on BST Insertions

Given the following sequence of insertions into an empty Binary Search Tree (BST), what is the output of an inorder traversal?

DSA Go

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, res *[]int) {
    if root == nil {
        return
    }
    inorder(root.left, res)
    *res = append(*res, root.val)
    inorder(root.right, res)
}

func main() {
    var root *Node
    values := []int{50, 30, 70, 20, 40, 60, 80}
    for _, v := range values {
        root = insert(root, v)
    }
    var result []int
    inorder(root, &result)
    fmt.Println(result)
}

A [20, 40, 30, 60, 80, 70, 50]

B [20, 30, 40, 50, 60, 70, 80]

C [80, 70, 60, 50, 40, 30, 20]

D [50, 30, 20, 40, 70, 60, 80]

💡 Hint

Inorder traversal of a BST always returns values in sorted order.

Inorder traversal visits nodes in ascending order for BSTs. The inserted values will be sorted as [20, 30, 40, 50, 60, 70, 80].

🧠 Conceptual

intermediate

Why Use BST Over Hash Map for Ordered Data?

Which of the following is the main reason to choose a Binary Search Tree (BST) over a Hash Map when you need ordered data?

A BST maintains elements in sorted order allowing range queries and ordered traversal.

B BST provides faster average lookup time than Hash Map.

C BST uses less memory than Hash Map in all cases.

D BST automatically handles duplicate keys better than Hash Map.

💡 Hint

Think about what data structure allows you to get sorted data easily.

BST keeps data sorted by design, enabling ordered traversal and range queries, which Hash Maps do not support natively.

❓ Predict Output

advanced

Hash Map Key Existence Check Output

What is the output of the following Go code snippet that uses a map to check key existence?

DSA Go

package main

import "fmt"

func main() {
    m := map[int]string{1: "one", 2: "two", 3: "three"}
    val, ok := m[4]
    fmt.Println(val, ok)
}

A panic: runtime error: invalid memory address or nil pointer dereference

B "four" true

C "zero" false

D "" false

💡 Hint

Accessing a non-existent key in a Go map returns zero value and false for existence.

When a key is not found in a Go map, the zero value of the value type is returned along with false.

🚀 Application

advanced

Choosing Data Structure for Range Queries

You need to store a large set of integer keys and frequently perform queries to find all keys within a given range. Which data structure is best suited for this task?

A Binary Search Tree (BST) because it supports efficient range queries via inorder traversal.

B Hash Map because it provides constant time lookup for any key.

C Array because it allows direct indexing of keys.

D Stack because it supports last-in-first-out access.

💡 Hint

Think about which structure keeps keys sorted and allows scanning between two values.

BSTs keep keys sorted and allow efficient traversal of keys in a range, unlike Hash Maps or stacks.

🔧 Debug

expert

Why Does This BST Insertion Cause Infinite Recursion?

Consider this Go code for inserting into a BST. Why does it cause infinite recursion?

DSA Go

func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val <= root.val {
        insert(root.left, val)
    } else {
        insert(root.right, val)
    }
    return root
}

A Because the function does not handle duplicate values correctly.

B Because the base case is missing for nil root.

C Because the recursive calls do not assign the returned node back to root.left or root.right.

D Because the function returns root before recursion completes.

💡 Hint

Check if the recursive calls update the tree links properly.

The recursive calls must assign the returned node to root.left or root.right to update the tree; otherwise, the tree structure is never updated, causing infinite recursion.

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