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

Mental Model

A BST keeps data sorted and lets you find items in order, while a hash map finds items fast but doesn't keep order.

Analogy: Think of a BST like a sorted bookshelf where books are arranged by title, so you can quickly find books in order. A hash map is like a pile of books with labels, where you find a book fast by its label but the pile is messy and unordered.

BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

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

Dry Run Walkthrough

Input: Insert values 4, 2, 6, 1, 3, 5, 7 into BST and hash map; then search for 5 and get sorted order

Goal: Show how BST keeps data sorted and allows ordered traversal, while hash map allows fast search but no order

Step 1: Insert 4 into BST and hash map

BST: 4 -> null
Hash Map: [hash(4)]=4

Why: Start with root node in BST and store 4 in hash map bucket

Step 2: Insert 2 into BST and hash map

BST: 4 -> 2 (left child)
Hash Map: [hash(2)]=2, [hash(4)]=4

Why: 2 is less than 4, so goes left in BST; hash map stores 2 in its bucket

Step 3: Insert 6 into BST and hash map

BST: 4 -> 2 (left), 6 (right)
Hash Map: [hash(6)]=6, [hash(2)]=2, [hash(4)]=4

Why: 6 is greater than 4, so goes right in BST; hash map stores 6

Step 4: Insert 1, 3, 5, 7 similarly

BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7
Hash Map: buckets for 1,3,5,7 filled

Why: BST maintains order by placing smaller left, larger right; hash map stores all values in buckets

Step 5: Search for 5 in BST and hash map

BST search path: 4 -> 6 -> 5 found
Hash Map: direct access to bucket for 5

Why: BST search takes steps following tree links; hash map finds 5 instantly by hash

Step 6: Traverse BST inorder to get sorted data

BST inorder traversal: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Hash Map: no order guaranteed

Why: BST inorder traversal visits nodes in sorted order; hash map has no order

Result:

BST final: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Hash Map final: unordered buckets with all values
Search result: 5 found in both

Annotated Code

DSA Python

class BSTNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = BSTNode(val)
            return
        curr = self.root
        while True:
            if val < curr.val:
                if curr.left is None:
                    curr.left = BSTNode(val)
                    return
                curr = curr.left
            else:
                if curr.right is None:
                    curr.right = BSTNode(val)
                    return
                curr = curr.right

    def inorder(self):
        result = []
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        dfs(self.root)
        return result

    def search(self, val):
        curr = self.root
        while curr:
            if val == curr.val:
                return True
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return False

class HashMap:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        return key % self.size

    def insert(self, key):
        idx = self._hash(key)
        if key not in self.buckets[idx]:
            self.buckets[idx].append(key)

    def search(self, key):
        idx = self._hash(key)
        return key in self.buckets[idx]

# Driver code
values = [4, 2, 6, 1, 3, 5, 7]

bst = BST()
hash_map = HashMap()

for v in values:
    bst.insert(v)  # insert into BST
    hash_map.insert(v)  # insert into hash map

search_val = 5
bst_found = bst.search(search_val)
hash_found = hash_map.search(search_val)

bst_sorted = bst.inorder()

print("BST inorder:", " -> ".join(map(str, bst_sorted)) + " -> null")
print(f"Search {search_val} in BST: {bst_found}")
print(f"Search {search_val} in Hash Map: {hash_found}")

if not self.root: self.root = BSTNode(val) return

set root if tree empty

while True: if val < curr.val: if curr.left is None: curr.left = BSTNode(val) return curr = curr.left else: if curr.right is None: curr.right = BSTNode(val) return curr = curr.right

traverse BST to find correct insert position

def dfs(node): if not node: return dfs(node.left) result.append(node.val) dfs(node.right)

inorder traversal to collect sorted values

while curr: if val == curr.val: return True elif val < curr.val: curr = curr.left else: curr = curr.right return False

search BST by traversing left or right

idx = self._hash(key) if key not in self.buckets[idx]: self.buckets[idx].append(key)

insert key into hash map bucket if not present

idx = self._hash(key) return key in self.buckets[idx]

search key in hash map bucket

Output

BST inorder: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null

Search 5 in BST: True

Search 5 in Hash Map: True

Complexity Analysis

Time: O(n) for building BST and hash map; O(log n) average for BST search; O(1) average for hash map search

Space: O(n) for both BST and hash map to store n elements

vs Alternative: BST keeps data sorted allowing ordered traversal but search can be slower; hash map offers faster search but no order

Edge Cases

Empty data structures

Search returns False; traversal returns empty list

DSA Python

if not self.root:
    self.root = BSTNode(val)
    return

Duplicate values inserted

BST inserts duplicates to right subtree; hash map avoids duplicates in bucket

DSA Python

if key not in self.buckets[idx]:
    self.buckets[idx].append(key)

Search for value not present

Both BST and hash map return False

DSA Python

return False

When to Use This Pattern

When you need to keep data sorted and also search efficiently, consider BST; if order doesn't matter and you want fastest search, use hash map.

Common Mistakes

Mistake: Assuming hash map keeps data sorted
Fix: Remember hash maps do not maintain order; use BST for sorted data

Mistake: Not handling duplicates in hash map buckets
Fix: Check if key exists before inserting to avoid duplicates

Summary

BST stores data in sorted order allowing ordered traversal and search.

Use BST when you need sorted data and range queries; use hash map when you need fastest search without order.

BST trades search speed for order; hash map trades order for speed.

Practice

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

easy

A. Binary Search Tree (BST)

B. Hash Map

C. Stack

D. Queue

Solution

1. Step 1: Understand the need for sorted order

   Maintaining sorted order requires a data structure that keeps elements in order as they are inserted.

2. Step 2: Compare BST and Hash Map for range queries

   BST supports in-order traversal and range queries efficiently, while Hash Map does not maintain order.

3. Final Answer:

   Binary Search Tree (BST) -> Option A

4. Quick Check:

   Sorted order + range queries = BST [OK]

Hint: Sorted data with range queries? Think BST first. [OK]

Common Mistakes:

• Choosing Hash Map for ordered data
• Confusing Stack or Queue with ordered structures
• Ignoring the need for range queries

2. Which of the following is the correct way to declare a Hash Map (dictionary) in Python?

easy

A. hash_map = ()

B. hash_map = []

C. hash_map = {}

D. hash_map = set()

Solution

1. Step 1: Recall Python syntax for dictionary

   In Python, dictionaries (hash maps) are declared using curly braces {}.

2. Step 2: Identify correct option

   hash_map = {} uses {}, which is the correct syntax for an empty dictionary.

3. Final Answer:

   hash_map = {} -> Option C

4. Quick Check:

   Empty dictionary = {} [OK]

Hint: Empty dictionary uses curly braces {} in Python. [OK]

Common Mistakes:

• Using [] which creates a list
• Using () which creates a tuple
• Using set() which creates a set, not a dictionary

3. What will be the output of the following Python code?

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def inorder(root, result):
    if root:
        inorder(root.left, result)
        result.append(root.key)
        inorder(root.right, result)

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)

result = []
inorder(root, result)
print(result)

medium

A. [5, 2, 7, 10, 15]

B. [10, 5, 2, 7, 15]

C. [15, 10, 7, 5, 2]

D. [2, 5, 7, 10, 15]

Solution

1. Step 1: Understand inorder traversal

   Inorder traversal visits left subtree, root, then right subtree, producing sorted keys in BST.

2. Step 2: Trace the traversal on given tree

   Nodes visited in order: 2 (leftmost), 5, 7, 10 (root), 15 (right child).

3. Final Answer:

   [2, 5, 7, 10, 15] -> Option D

4. Quick Check:

   Inorder traversal = sorted keys [OK]

Hint: Inorder traversal of BST gives sorted list. [OK]

Common Mistakes:

• Confusing preorder or postorder traversal
• Ignoring left subtree first
• Appending keys in wrong order

4. The following code attempts to insert keys into a BST but has a bug. What is the error?

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        insert(root.left, key)
    else:
        insert(root.right, key)
    return root

root = None
root = insert(root, 10)
root = insert(root, 5)
root = insert(root, 15)

medium

A. The base case does not create a new node

B. The insert function does not assign returned nodes to root.left or root.right

C. The comparison operator should be <= instead of <

D. The function should return None at the end

Solution

1. Step 1: Analyze insert function behavior

   Recursive calls to insert do not update root.left or root.right with returned nodes.

2. Step 2: Identify missing assignment

   Without assigning, new nodes are created but not linked to the tree, so tree structure breaks.

3. Final Answer:

   The insert function does not assign returned nodes to root.left or root.right -> Option B

4. Quick Check:

   Missing assignment in recursion = bug [OK]

Hint: Always assign recursive insert results to child pointers. [OK]

Common Mistakes:

• Ignoring returned node from recursive insert
• Thinking base case is wrong
• Changing comparison operator unnecessarily

5. You need to store a large dataset of user IDs with associated scores. You want to quickly find users by ID and also retrieve users sorted by their scores. Which combination of data structures is best?

hard

A. Use a Hash Map for ID lookup and a Balanced BST keyed by score for sorting

B. Use only a Hash Map keyed by score

C. Use only a BST keyed by user ID

D. Use a list sorted by user ID

Solution

1. Step 1: Identify requirements for fast lookup and sorted retrieval

   Fast lookup by user ID suggests Hash Map; sorted retrieval by score suggests BST keyed by score.

2. Step 2: Evaluate options

   Use a Hash Map for ID lookup and a Balanced BST keyed by score for sorting uses Hash Map for O(1) ID lookup and BST for ordered score retrieval, meeting both needs efficiently.

3. Final Answer:

   Use a Hash Map for ID lookup and a Balanced BST keyed by score for sorting -> Option A

4. Quick Check:

   Hash Map + BST combo = best for lookup + sorted data [OK]

Hint: Combine Hash Map for keys and BST for sorted order. [OK]

Common Mistakes:

• Using only one data structure for both needs
• Using list which is slow for lookup
• Using BST keyed by ID only, ignoring score sorting