Searching in BST in Data Structures Theory - Mini Project: Build & Apply

Searching in BST

📖 Scenario: You have a collection of numbers stored in a special tree called a Binary Search Tree (BST). This tree helps you find numbers quickly by following simple rules.Imagine you want to check if a certain number is in your collection.

🎯 Goal: Build a step-by-step process to search for a number in a Binary Search Tree (BST) by following the BST rules.

📋 What You'll Learn

Create a simple BST structure with nodes and values

Set a target value to search for

Use the BST search logic to find the target

Complete the search by returning the result

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to quickly find data without searching everything.

💼 Career

Understanding BST search is important for software developers working with data structures and algorithms.

1

Create the BST nodes

Create a dictionary called bst representing a simple BST with this structure: root node value 8, left child value 3, right child value 10. Use nested dictionaries with keys value, left, and right. Set children to None if no child exists.

Data Structures Theory

# Create the bst dictionary with root 8, left child 3, right child 10
# Your code here

Need a hint?

Use nested dictionaries to represent nodes. Each node has 'value', 'left', and 'right' keys.

2

Set the target value to search

Create a variable called target and set it to the number 10 which you want to find in the BST.

Data Structures Theory

bst = {
    'value': 8,
    'left': {'value': 3, 'left': None, 'right': None},
    'right': {'value': 10, 'left': None, 'right': None}
}
# Set the target value to 10
# Your code here

Need a hint?

Just assign the number 10 to the variable named target.

3

Implement the BST search logic

Write a function called search_bst that takes two arguments: node and target. Use the BST search rules: if node is None, return False. If node['value'] equals target, return True. If target is less than node['value'], search the left child. Otherwise, search the right child.

Data Structures Theory

bst = {
    'value': 8,
    'left': {'value': 3, 'left': None, 'right': None},
    'right': {'value': 10, 'left': None, 'right': None}
}
target = 10

# Define the search_bst function using BST rules
# Your code here

Need a hint?

Use recursion to check left or right child based on comparison.

4

Complete the search by calling the function

Create a variable called found and set it to the result of calling search_bst with bst and target as arguments.

Data Structures Theory

bst = {
    'value': 8,
    'left': {'value': 3, 'left': None, 'right': None},
    'right': {'value': 10, 'left': None, 'right': None}
}
target = 10

def search_bst(node, target):
    if node is None:
        return False
    if node['value'] == target:
        return True
    if target < node['value']:
        return search_bst(node['left'], target)
    else:
        return search_bst(node['right'], target)

# Store the search result in found
# Your code here

Need a hint?

Call the function with the root node and target, save the result in found.