BST vs Hash Map Trade-offs for Ordered Data in DSA Python - Build Both Approaches

BST vs Hash Map Trade-offs for Ordered Data

📖 Scenario: Imagine you are managing a small library's book collection. You want to store book titles and their number of copies. You need to quickly find how many copies a book has, but also sometimes list all books in alphabetical order.

🎯 Goal: You will create a dictionary to store book titles and copies, then add a helper variable to decide if you want ordered output. Next, you will write code to print the books in alphabetical order using sorting (simulating ordered data like a BST) or directly from the dictionary (like a hash map). Finally, you will print the result.

📋 What You'll Learn

Create a dictionary called books with exact entries: 'Moby Dick': 3, 'Hamlet': 5, 'War and Peace': 2, '1984': 4

Create a boolean variable called ordered and set it to True

Use an if statement to check ordered. If True, create a list sorted_books with book titles sorted alphabetically. Otherwise, use the dictionary keys as is.

Print the book titles and copies in the chosen order, each line as title: copies

💡 Why This Matters

🌍 Real World

Libraries, stores, and apps often need to store items with quick lookup and sometimes show them in order. Choosing the right data structure helps balance speed and order.

💼 Career

Understanding when to use hash maps or trees is key for software developers, data engineers, and anyone working with data storage and retrieval.

1

Create the book collection dictionary

Create a dictionary called books with these exact entries: 'Moby Dick': 3, 'Hamlet': 5, 'War and Peace': 2, '1984': 4

DSA Python

# Create the books dictionary with exact entries
# Your code here

Hint

Use curly braces {} to create a dictionary. Put each book title as a key and number of copies as the value.

2

Add a variable to choose ordered output

Create a boolean variable called ordered and set it to True

DSA Python

books = {'Moby Dick': 3, 'Hamlet': 5, 'War and Peace': 2, '1984': 4}
# Create the ordered variable and set it to True
# Your code here

Hint

Use ordered = True to create the variable.

3

Select order and prepare list of book titles

Use an if statement to check if ordered is True. If yes, create a list called sorted_books with the book titles sorted alphabetically using sorted(books.keys()). Otherwise, create sorted_books as a list of the dictionary keys without sorting.

DSA Python

books = {'Moby Dick': 3, 'Hamlet': 5, 'War and Peace': 2, '1984': 4}
ordered = True
# Use if to create sorted_books list based on ordered
# Your code here

Hint

Use sorted() to get alphabetical order. Use list() to get keys as a list without sorting.

4

Print the books and their copies in chosen order

Use a for loop with variable title to iterate over sorted_books. Inside the loop, print the book title and copies in the format title: copies using print(f"{title}: {books[title]}")

DSA Python

books = {'Moby Dick': 3, 'Hamlet': 5, 'War and Peace': 2, '1984': 4}
ordered = True
if ordered:
    sorted_books = sorted(books.keys())
else:
    sorted_books = list(books.keys())
# Print each book title and copies in sorted_books
# Your code here

Hint

Use a for loop and f-string to print each book and its copies.

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