BST Search Operation in DSA Python - Build from Scratch

BST Search Operation

📖 Scenario: You are working with a phone book stored as a Binary Search Tree (BST). Each node contains a contact's name as the key and their phone number as the value. You want to find if a contact exists in the phone book.

🎯 Goal: Build a simple BST search operation that looks for a contact's name and returns their phone number if found, or None if not.

📋 What You'll Learn

Create a BST node class with name, phone, left, and right attributes

Manually create a small BST with 3 contacts

Write a search function that takes the root node and a contact name, and returns the phone number or None

Print the result of searching for a specific contact

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and many databases use BSTs or similar trees to quickly find information by key.

💼 Career

Understanding BST search is fundamental for software engineers working with data storage, search engines, and efficient data retrieval.

1

Create BST Node Class and Tree

Create a class called BSTNode with an __init__ method that takes name and phone as parameters and sets self.left and self.right to None. Then create three nodes: root with name 'John' and phone '555-1234', left_child with name 'Alice' and phone '555-2345', and right_child with name 'Zara' and phone '555-3456'. Link left_child as root.left and right_child as root.right.

DSA Python

# Define BSTNode class and create root, left_child, right_child nodes
# Your code here

Hint

Remember to set self.left and self.right to None in the constructor.

2

Set Search Target Name

Create a variable called target_name and set it to the string 'Alice'.

DSA Python

class BSTNode:
    def __init__(self, name, phone):
        self.name = name
        self.phone = phone
        self.left = None
        self.right = None

root = BSTNode('John', '555-1234')
left_child = BSTNode('Alice', '555-2345')
right_child = BSTNode('Zara', '555-3456')
root.left = left_child
root.right = right_child

# Set the target_name to search for
# Your code here

Hint

Just create a variable target_name and assign the string 'Alice'.

3

Write BST Search Function

Define a function called bst_search that takes two parameters: node and name. Inside the function, if node is None, return None. If node.name equals name, return node.phone. If name is less than node.name, recursively call bst_search on node.left and name. Otherwise, recursively call bst_search on node.right and name. Assign the result of bst_search(root, target_name) to a variable called result.

DSA Python

class BSTNode:
    def __init__(self, name, phone):
        self.name = name
        self.phone = phone
        self.left = None
        self.right = None

root = BSTNode('John', '555-1234')
left_child = BSTNode('Alice', '555-2345')
right_child = BSTNode('Zara', '555-3456')
root.left = left_child
root.right = right_child

target_name = 'Alice'

# Define bst_search function and call it with root and target_name
# Your code here

Hint

Use recursion to search left or right subtree based on comparison.

4

Print Search Result

Print the value of the variable result.

DSA Python

class BSTNode:
    def __init__(self, name, phone):
        self.name = name
        self.phone = phone
        self.left = None
        self.right = None

root = BSTNode('John', '555-1234')
left_child = BSTNode('Alice', '555-2345')
right_child = BSTNode('Zara', '555-3456')
root.left = left_child
root.right = right_child

target_name = 'Alice'

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

result = bst_search(root, target_name)

# Print the result
# Your code here

Hint

Use print(result) to show the phone number found.

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