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

Mental Model

A Binary Search Tree keeps data sorted and allows ordered operations, while a Hash Map stores data for fast access but without order.

Analogy: Think of a phone book (BST) where names are in alphabetical order so you can find the next or previous name easily, versus a pile of index cards (Hash Map) where you can quickly find a name but the cards are not sorted.

BST:
      5
     / \
    3   7
   /     \
  2       9

Hash Map:
[0]: null
[1]: 7
[2]: 3
[3]: 9
[4]: 5
[5]: 2

Dry Run Walkthrough

Input: Insert keys 5, 3, 7, 2, 9 into BST and Hash Map; then find the next higher key after 5.

Goal: Show how BST supports ordered queries like 'next higher key' easily, while Hash Map does not.

Step 1: Insert 5 into BST and Hash Map

BST: 5 -> null
Hash Map: [4]:5

Why: Start with first key in both structures

Step 2: Insert 3 into BST and Hash Map

BST: 5 -> 3 (left child)
Hash Map: [4]:5, [2]:3

Why: BST places 3 left of 5 to keep order; Hash Map stores at hash index

Step 3: Insert 7 into BST and Hash Map

BST: 5 -> 3 (left), 7 (right)
Hash Map: [4]:5, [2]:3, [1]:7

Why: BST places 7 right of 5; Hash Map stores at hash index

Step 4: Insert 2 into BST and Hash Map

BST: 5 -> 3 -> 2 (left-left)
Hash Map: [4]:5, [2]:3, [1]:7, [5]:2

Why: BST keeps 2 left of 3; Hash Map stores at hash index

Step 5: Insert 9 into BST and Hash Map

BST: 5 -> 3 (left), 7 -> 9 (right-right)
Hash Map: [4]:5, [2]:3, [1]:7, [5]:2, [3]:9

Why: BST keeps 9 right of 7; Hash Map stores at hash index

Step 6: Find next higher key after 5 in BST

BST traversal: from 5, go right to 7
Next higher key is 7

Why: BST structure allows ordered traversal to find next higher key

Step 7: Try to find next higher key after 5 in Hash Map

Hash Map has no order; must check all keys to find min key > 5
Result: 7 after scanning all keys

Why: Hash Map lacks order, so ordered queries are costly

Result:

BST final: 5 -> 3 -> 2 (left subtree), 7 -> 9 (right subtree)
Hash Map final: keys stored at various indices
Next higher key after 5: BST=7, Hash Map=7 (found by scanning all keys)

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type BSTNode struct {
	key   int
	left  *BSTNode
	right *BSTNode
}

func insertBST(root *BSTNode, key int) *BSTNode {
	if root == nil {
		return &BSTNode{key: key}
	}
	if key < root.key {
		root.left = insertBST(root.left, key) // go left to keep order
	} else if key > root.key {
		root.right = insertBST(root.right, key) // go right to keep order
	}
	return root
}

func findNextHigherBST(root *BSTNode, key int) *BSTNode {
	var successor *BSTNode
	curr := root
	for curr != nil {
		if key < curr.key {
			successor = curr // potential next higher
			curr = curr.left // go left to find smaller candidate
		} else {
			curr = curr.right // go right to find larger keys
		}
	}
	return successor
}

// Simple Hash Map using Go map
func insertHashMap(m map[int]bool, key int) {
	m[key] = true
}

func findNextHigherHashMap(m map[int]bool, key int) (int, bool) {
	next := 0
	found := false
	for k := range m {
		if k > key {
			if !found || k < next {
				next = k
				found = true
			}
		}
	}
	return next, found
}

func main() {
	keys := []int{5, 3, 7, 2, 9}

	// Build BST
	var root *BSTNode
	for _, k := range keys {
		root = insertBST(root, k)
	}

	// Build Hash Map
	hashMap := make(map[int]bool)
	for _, k := range keys {
		insertHashMap(hashMap, k)
	}

	// Find next higher key after 5
	bstSucc := findNextHigherBST(root, 5)
	if bstSucc != nil {
		fmt.Printf("BST next higher key after 5: %d\n", bstSucc.key)
	} else {
		fmt.Println("BST no next higher key after 5")
	}

	hashSucc, found := findNextHigherHashMap(hashMap, 5)
	if found {
		fmt.Printf("Hash Map next higher key after 5: %d\n", hashSucc)
	} else {
		fmt.Println("Hash Map no next higher key after 5")
	}
}

if key < root.key { root.left = insertBST(root.left, key) // go left to keep order } else if key > root.key { root.right = insertBST(root.right, key) // go right to keep order }

insert key in BST maintaining order by going left or right

for curr != nil { if key < curr.key { successor = curr // potential next higher curr = curr.left // go left to find smaller candidate } else { curr = curr.right // go right to find larger keys } }

find next higher key by traversing BST and tracking successor

for k := range m { if k > key { if !found || k < next { next = k found = true } } }

scan all keys in Hash Map to find minimal key greater than given key

Output

BST next higher key after 5: 7

Hash Map next higher key after 5: 7

Complexity Analysis

Time: O(log n) average for BST operations because tree height is log n; O(n) worst if unbalanced; O(1) average for Hash Map insert/find but O(n) for ordered queries

Space: O(n) for both BST and Hash Map to store n keys

vs Alternative: BST supports ordered queries efficiently but slower insert/find than Hash Map; Hash Map is faster for exact key lookup but cannot do ordered queries without scanning all keys

Edge Cases

Empty BST and Hash Map

No next higher key found; functions return nil or false

DSA Go

if bstSucc != nil { ... } else { ... } in main

Next higher key does not exist (e.g., after 9)

BST returns nil successor; Hash Map returns false found flag

DSA Go

if bstSucc != nil { ... } else { ... } in main

Duplicate keys insertion

BST ignores duplicates; Hash Map overwrites existing key

DSA Go

if key < root.key { ... } else if key > root.key { ... } in insertBST

When to Use This Pattern

When a problem requires both fast lookup and ordered data access, consider BST for order and Hash Map for speed; knowing their trade-offs helps pick the right structure.

Common Mistakes

Mistake: Assuming Hash Map can efficiently find next higher key without scanning all keys
Fix: Use BST or another ordered structure for efficient ordered queries

Mistake: Not handling duplicates in BST insert causing infinite recursion
Fix: Add condition to ignore or handle equal keys in insertBST

Summary

BST keeps data sorted and supports ordered queries efficiently.

Use BST when you need to find next higher or lower keys quickly.

The key insight is BST structure allows ordered traversal, unlike Hash Map.

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