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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why choose a BST over a Hash Map for ordered data?

Which reason best explains why a Binary Search Tree (BST) might be preferred over a Hash Map when working with ordered data?

A BSTs maintain elements in sorted order, allowing in-order traversal to access data sequentially.

B Hash Maps always use less memory than BSTs, so they are better for ordered data.

C BSTs provide constant time lookup, which Hash Maps cannot guarantee.

D Hash Maps automatically keep keys sorted, so BSTs are unnecessary.

💡 Hint

Think about how each structure stores and accesses data in order.

BSTs keep data sorted by design, enabling ordered operations like range queries and sorted traversal. Hash Maps do not maintain order.

❓ Predict Output

intermediate

Output of in-order traversal vs hash map keys

Given the following data inserted into a BST and a Hash Map, what is the output of an in-order traversal of the BST and the list of keys from the Hash Map?

DSA Python

data = [50, 30, 70, 20, 40, 60, 80]

# BST in-order traversal output
# Hash Map keys output (order not guaranteed)

A BST in-order: 50 -> 30 -> 70 -> 20 -> 40 -> 60 -> 80 -> null; Hash Map keys: [20, 30, 40, 50, 60, 70, 80]

B BST in-order: 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null; Hash Map keys: [50, 30, 70, 20, 40, 60, 80]

C BST in-order: 80 -> 70 -> 60 -> 50 -> 40 -> 30 -> 20 -> null; Hash Map keys: [80, 70, 60, 50, 40, 30, 20]

D BST in-order: 20 -> 40 -> 30 -> 50 -> 60 -> 80 -> 70 -> null; Hash Map keys: [30, 50, 70, 20, 40, 60, 80]

💡 Hint

Recall that BST in-order traversal visits nodes from smallest to largest.

In-order traversal of BST visits nodes in ascending order. Hash Map keys have no guaranteed order.

🔧 Debug

advanced

Why does this BST code fail to maintain order?

Consider this simplified BST insertion code snippet. Why does it fail to keep the tree ordered?

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

def insert(root, val):
    if root is None:
        return Node(val)
    if val > root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

A The function does not handle the case when root is None.

B The function inserts duplicates incorrectly by ignoring them.

C The comparison signs are reversed; values greater than root should go to the right subtree.

D The function should return None instead of root after insertion.

💡 Hint

Check which subtree the greater values are inserted into.

In a BST, values greater than the current node go to the right subtree, but here they are inserted into the left subtree, breaking order.

🚀 Application

advanced

Choosing data structure for range queries on ordered data

You need to frequently find all keys between two values in a large dataset. Which data structure is best suited for this task?

A Stack, because it supports last-in-first-out operations.

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

C Array, because it allows direct index access to elements.

D Binary Search Tree, because it supports efficient in-order traversal and range queries.

💡 Hint

Think about which structure keeps data sorted and allows sequential access.

BSTs keep data sorted and allow efficient range queries by traversing nodes between two values. Hash Maps do not maintain order, so range queries are inefficient.

❓ Predict Output

expert

Output after mixed BST and Hash Map operations

Given the following operations, what is the final printed output?

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

def insert(root, val):
    if root is None:
        return BSTNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

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

# Insert into BST
root = None
for v in [40, 20, 60, 10, 30, 50, 70]:
    root = insert(root, v)

# Create Hash Map
hmap = {}
for v in [40, 20, 60, 10, 30, 50, 70]:
    hmap[v] = v * 2

# Remove key 60 from Hash Map
hmap.pop(60)

# Print BST in-order
bst_result = []
inorder(root, bst_result)
print('BST:', ' -> '.join(map(str, bst_result)) + ' -> null')

# Print Hash Map keys sorted
print('Hash Map keys:', sorted(hmap.keys()))

A

BST: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> null
Hash Map keys: [10, 20, 30, 40, 50, 70]

B

BST: 70 -> 60 -> 50 -> 40 -> 30 -> 20 -> 10 -> null
Hash Map keys: [10, 20, 30, 40, 50, 60, 70]

C

BST: 10 -> 20 -> 30 -> 40 -> 50 -> 70 -> null
Hash Map keys: [10, 20, 30, 40, 50, 70]

D

BST: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> null
Hash Map keys: [10, 20, 30, 40, 50, 60]

💡 Hint

Trace the BST insertion and Hash Map removal carefully.

The BST in-order traversal prints all inserted values in ascending order. The Hash Map has key 60 removed, so it is missing from the keys list.

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