BST Search Operation in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current node is None in the BST search function.

DSA Python

def search_bst(node, target):
    if node [1] None:
        return False

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

A<

B==

C!=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' instead of '==' causes wrong logic.

Using comparison operators like '>' or '<' with None causes errors.

We check if the node is equal to None to know if we've reached a leaf without finding the target.

2fill in blank

medium

Complete the code to return True if the current node's value matches the target.

DSA Python

def search_bst(node, target):
    if node is None:
        return False
    if node.val [1] target:
        return True

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

A!=

B>

C<

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' instead of '==' causes incorrect results.

Using '<' or '>' here is incorrect for equality check.

We return True when the node's value equals the target value.

3fill in blank

hard

Fix the error in the recursive call to search the left subtree when target is less than node's value.

DSA Python

def search_bst(node, target):
    if node is None:
        return False
    if node.val == target:
        return True
    if target < node.val:
        return search_bst([1], target)

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

Anode

Bnode.right

Cnode.left

Dtarget.left

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.right searches the wrong subtree.

Using node or target.left causes errors.

When target is less than node's value, we search the left child subtree.

4fill in blank

hard

Fill both blanks to complete the recursive call to search the right subtree when target is greater than node's value.

DSA Python

def search_bst(node, target):
    if node is None:
        return False
    if node.val == target:
        return True
    if target > node.val:
        return [1]([2], target)

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

Asearch_bst

Bnode.right

Cnode.left

Dsearch_tree

Attempts:

3 left

💡 Hint

Common Mistakes

Using search_tree instead of search_bst causes errors.

Using node.left searches the wrong subtree.

We call the search function recursively on the right child when target is greater.

5fill in blank

hard

Fill all three blanks to complete the full BST search function.

DSA Python

def search_bst(node, target):
    if node [1] None:
        return False
    if node.val [2] target:
        return True
    if target < node.val:
        return search_bst(node.left, target)
    else:
        return search_bst([3], target)

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

A==

B!=

Dnode.right

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' instead of '==' in the first condition.

Using wrong variable for right subtree search.

The function checks if node is None, then if node.val equals target, and finally searches left or right subtree accordingly.

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