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.