BST vs Hash Map Trade-offs for Ordered Data in DSA Python - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a value into a BST node.

DSA Python

if root is None:
    root = [1](key)
else:
    # Insert recursively

Drag options to blanks, or click blank then click option'

Adict

BNode

Clist

Dset

Attempts:

3 left

💡 Hint

Common Mistakes

Using a dictionary or list instead of a Node object.

Trying to insert without creating a new node.

We create a new Node instance to insert into the BST when the root is None.

2fill in blank

medium

Complete the code to check if a key exists in a hash map.

DSA Python

if [1] in hashmap:
    print('Found')
else:
    print('Not found')

Drag options to blanks, or click blank then click option'

Avalue

Bnode

Citem

Dkey

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for a value instead of a key.

Using variable names that don't represent keys.

We check if the key exists in the hash map using the in keyword.

3fill in blank

hard

Fix the error in the BST search function by completing the blank.

DSA Python

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < [1].key:
        return search(root.left, key)
    else:
        return search(root.right, key)

Drag options to blanks, or click blank then click option'

Aroot

Bkey

Cnode

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the key variable instead of the node's key.

Using undefined variables like node or value.

The comparison should be with root.key to decide the search path in the BST.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that filters keys greater than 10.

DSA Python

{k: v for k, v in data.items() if k [1] 10 and v [2] 0}

Drag options to blanks, or click blank then click option'

A>

B<

C>=

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators that include unwanted keys or values.

Mixing up greater than and less than signs.

The comprehension keeps items where the key is greater than 10 and the value is not zero.

5fill in blank

hard

Fill all three blanks to create a BST insertion function snippet.

DSA Python

if root is None:
    return [1](key)
if key [2] root.key:
    root.left = insert(root.left, key)
else:
    root.right = insert(root.right, key)
return [3]

Drag options to blanks, or click blank then click option'

ANode

B<

Croot

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Returning the wrong variable at the end.

Using > instead of < for left subtree insertion.

We create a new Node if root is None, compare key with root.key using <, and finally return the root node.

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