Why BST enables efficient searching in Data Structures Theory - See It in Action

Why BST Enables Efficient Searching

📖 Scenario: Imagine you have a large phone book with names and numbers. You want to find a person's number quickly without flipping through every page.

🎯 Goal: Build a simple example that shows how a Binary Search Tree (BST) organizes data to make searching faster than looking through a list one by one.

📋 What You'll Learn

Create a small BST structure with exact nodes

Add a variable to hold the target value to search

Write the logic to search the BST for the target value

Complete the structure to show the search result conceptually

💡 Why This Matters

🌍 Real World

BSTs are used in databases, file systems, and search engines to quickly find data without scanning everything.

💼 Career

Understanding BSTs helps in software development roles that involve data organization, optimization, and algorithm design.

1

Create the BST nodes

Create a dictionary called bst representing a simple BST with these exact nodes: root node with value 15, left child 10, right child 20, left child of 10 is 8, and right child of 10 is 12.

Data Structures Theory

# Create the BST dictionary with exact nodes
# Your code here

Need a hint?

Think of the BST as a nested dictionary where each node has a value and optional left and right children.

2

Set the target value to search

Add a variable called target and set it to the integer 12 to represent the value we want to find in the BST.

Data Structures Theory

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

Need a hint?

The target is the number you want to find in the BST.

3

Write the search logic

Write a function called search_bst that takes two parameters: node and target. Use the BST property to search efficiently: 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': 15,
    'left': {
        'value': 10,
        'left': {'value': 8, 'left': None, 'right': None},
        'right': {'value': 12, 'left': None, 'right': None}
    },
    'right': {'value': 20, 'left': None, 'right': None}
}
target = 12
# Define the search_bst function below
# Your code here

Need a hint?

Use the BST rule: left child values are smaller, right child values are larger.

4

Complete with search result variable

Add 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': 15,
    'left': {
        'value': 10,
        'left': {'value': 8, 'left': None, 'right': None},
        'right': {'value': 12, 'left': None, 'right': None}
    },
    'right': {'value': 20, 'left': None, 'right': None}
}
target = 12

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

# Set found to the result of searching bst for target
# Your code here

Need a hint?

This variable shows if the target was found in the BST.