BST Search Operation in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Search for Existing Value

What is the output of the following code that searches for the value 15 in the BST?

DSA Python

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

def bst_search(root, target):
    if root is None:
        return False
    if root.val == target:
        return True
    elif target < root.val:
        return bst_search(root.left, target)
    else:
        return bst_search(root.right, target)

# Construct BST
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(30)

result = bst_search(root, 15)
print(result)

A Raises an error

B False

C None

D True

💡 Hint

Think about whether 15 exists in the tree nodes.

The value 15 exists in the BST as the left child of 20. The search function returns True when it finds the target.

❓ Predict Output

intermediate

Output of BST Search for Non-Existing Value

What is the output of the following code that searches for the value 25 in the BST?

DSA Python

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

def bst_search(root, target):
    if root is None:
        return False
    if root.val == target:
        return True
    elif target < root.val:
        return bst_search(root.left, target)
    else:
        return bst_search(root.right, target)

# Construct BST
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(30)

result = bst_search(root, 25)
print(result)

A None

B Raises an error

C False

D True

💡 Hint

Check if 25 is present in the BST nodes.

The value 25 does not exist in the BST. The search function returns False when the target is not found.

🧠 Conceptual

advanced

Understanding BST Search Path

In a BST, when searching for the value 7 starting from the root 10, which nodes will be visited in order?

A 10 -> 20 -> 15 -> 7

B 10 -> 5 -> 7

C 10 -> 5 -> 3 -> 7

D 10 -> 7

💡 Hint

Remember BST property: left child < parent < right child.

Starting at 10, since 7 < 10, go left to 5. Then 7 > 5, go right to 7. So nodes visited are 10, 5, 7.

🔧 Debug

advanced

Identify the Error in BST Search Implementation

What error will the following BST search code produce when searching for 15?

DSA Python

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

def bst_search(root, target):
    if root is None:
        return False
    if root.val == target:
        return True
    elif target > root.val:
        return bst_search(root.left, target)
    else:
        return bst_search(root.right, target)

# Construct BST
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(30)

result = bst_search(root, 15)
print(result)

A Returns False incorrectly

B Returns True correctly

C Raises AttributeError

D Infinite recursion leading to RecursionError

💡 Hint

Check the direction of recursive calls for target > root.val.

The code incorrectly searches left subtree when target > root.val, so it misses the correct node and returns False.

🚀 Application

expert

Number of Recursive Calls in BST Search

Given the BST below, how many recursive calls does bst_search make when searching for 3? BST structure: - Root: 8 - Left child of 8: 4 - Right child of 8: 12 - Left child of 4: 2 - Right child of 4: 6 - Left child of 2: 1 - Right child of 2: 3 Assume bst_search is defined as usual and counts the initial call as the first call.

DSA Python

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

def bst_search(root, target):
    if root is None:
        return False
    if root.val == target:
        return True
    elif target < root.val:
        return bst_search(root.left, target)
    else:
        return bst_search(root.right, target)

# Construct BST
root = Node(8)
root.left = Node(4)
root.right = Node(12)
root.left.left = Node(2)
root.left.right = Node(6)
root.left.left.left = Node(1)
root.left.left.right = Node(3)

# Count recursive calls
call_count = 0

def bst_search_count(root, target):
    global call_count
    call_count += 1
    if root is None:
        return False
    if root.val == target:
        return True
    elif target < root.val:
        return bst_search_count(root.left, target)
    else:
        return bst_search_count(root.right, target)

bst_search_count(root, 3)
print(call_count)

A 4

B 6

C 3

D 5

💡 Hint

Count each node visited from root to target.

The search visits nodes 8, 4, 2, then 3. That's 4 nodes, so 4 calls. But the initial call counts as 1, so total calls are 4.

Wait, initial call is the first call, so total calls = 4.

Recount: calls for nodes 8, 4, 2, 3 = 4 calls total.

Therefore, correct answer is 4.

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