Why BST Search Operation in DSA Python?

The Big Idea

What if you could find any name in a huge list in just a few quick steps instead of flipping endlessly?

The Scenario

Imagine you have a huge phone book with thousands of names and numbers. You want to find one person's number by flipping pages one by one from the start.

The Problem

Flipping pages one by one is slow and tiring. You might lose your place or flip too many pages. It wastes time and can cause mistakes.

The Solution

A Binary Search Tree (BST) helps by organizing names so you can quickly decide to go left or right, skipping many pages at once. This makes finding a name much faster and easier.

Before vs After

✗ Before

def find_number(phone_book, name):
    for entry in phone_book:
        if entry.name == name:
            return entry.number
    return None

✓ After

def search_bst(node, name):
    if node is None:
        return None
    if node.name == name:
        return node.number
    elif name < node.name:
        return search_bst(node.left, name)
    else:
        return search_bst(node.right, name)

What It Enables

It enables lightning-fast searching in sorted data by cutting down the search space at every step.

Real Life Example

When you search for a contact on your phone, the system uses a structure like BST to find the contact quickly without scrolling through the entire list.

Key Takeaways

Manual search is slow and error-prone.

BST organizes data to speed up search by choosing paths.

BST search reduces time from checking all items to just a few steps.

Practice

1. What is the main purpose of the search operation in a Binary Search Tree (BST)?

easy

A. To find whether a given value exists in the BST

B. To insert a new value into the BST

C. To delete a value from the BST

D. To traverse all nodes in the BST

Solution

1. Step 1: Understand the purpose of search in BST

   The search operation is used to check if a specific value is present in the BST.

2. Step 2: Differentiate from other operations

   Insertion adds new values, deletion removes values, and traversal visits all nodes. Search only checks for existence.

3. Final Answer:

   To find whether a given value exists in the BST -> Option A

4. Quick Check:

   Search = Find value [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert or delete
• Thinking search returns all nodes
• Assuming search modifies the tree

2. Which of the following is the correct Python function signature for a BST search method that takes a root node and a key to find?

easy

A. def search(key, root):

B. def search(key):

C. def search(root):

D. def search(root, key):

Solution

1. Step 1: Identify required parameters for BST search

   The search needs the root node to start and the key to find.

2. Step 2: Match parameters order

   Common convention is root first, then key, so def search(root, key): is correct.

3. Final Answer:

   def search(root, key): -> Option D

4. Quick Check:

   Function(root, key) correct signature [OK]

Hint: Root node first, key second in search function [OK]

Common Mistakes:

• Swapping parameter order
• Missing one parameter
• Using only one parameter

3. Given the following BST and the search function call search(root, 15), what will be the output?

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

def search(root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    return search(root.right, key)

root = Node(10)
root.left = Node(5)
root.right = Node(20)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.left = Node(15)
root.right.right = Node(25)

result = search(root, 15)
print(result.val if result else 'Not found')

medium

A. 15

B. 20

C. Not found

D. 10

Solution

1. Step 1: Trace search path for key 15

   Start at root (10). Since 15 > 10, go right to node 20. Then 15 < 20, go left to node 15.

2. Step 2: Check node value

   Node value is 15, matches key, so return this node.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Search found node with value 15 [OK]

Hint: Follow BST rules: left < node < right [OK]

Common Mistakes:

• Stopping search too early
• Going wrong direction at node 20
• Returning root value instead of found node

4. The following code is intended to search for a key in a BST, but it has a bug. What is the error?

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

medium

A. The function does not return anything

B. Missing base case for root is None

C. The recursive calls to left and right are swapped

D. The comparison operator should be >= instead of >

Solution

1. Step 1: Analyze recursive calls

   For BST, if key > root.val, search should go right subtree, but code calls search(root.left, key).

2. Step 2: Identify correct direction

   Correct is to go right when key > root.val and left when key < root.val.

3. Final Answer:

   The recursive calls to left and right are swapped -> Option C

4. Quick Check:

   Swap left/right calls to fix search [OK]

Hint: Remember: key > node means go right subtree [OK]

Common Mistakes:

• Swapping left and right recursive calls
• Forgetting base case for None
• Incorrect comparison operators

5. You want to search for the value 8 in the BST below. Which sequence of nodes will the search visit?

BST structure:
10
/ \
5 15
/ \ \
3 7 20

Choose the correct sequence of visited nodes for search(root, 8).

hard

A. [10, 5, 7]

B. [10, 5, 7, None]

C. [10, 15, 20]

D. [10, 5, 3]

Solution

1. Step 1: Start at root and compare with 8

   8 < 10, go left to 5.

2. Step 2: Compare with 5 and go right

   8 > 5, go right to 7.

3. Step 3: Compare with 7 and go right

   8 > 7, go right which is None (no node), search ends.

4. Final Answer:

   [10, 5, 7, None] -> Option B

5. Quick Check:

   Search path includes None when key not found [OK]

Hint: Follow path until None if key missing [OK]

Common Mistakes:

• Stopping at last node without None
• Going left instead of right at 7
• Ignoring None as end of search