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

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

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

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

Hint

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

Practice

1. Why does a Binary Search Tree (BST) enable faster searching compared to a simple list?

easy

A. Because it stores all elements in a single linked list

B. Because it stores data in a random order

C. Because it allows skipping half of the remaining elements at each step

D. Because it uses hashing to find elements instantly

Solution

1. Step 1: Understand BST search process

   A BST compares the search value with the current node and decides to go left or right, effectively skipping half the tree each time.

2. Step 2: Compare with list search

   In a simple list, you check elements one by one, but BST lets you ignore large parts quickly.

3. Final Answer:

   Because it allows skipping half of the remaining elements at each step -> Option C

4. Quick Check:

   BST halves search space each step = faster search [OK]

Hint: BST halves search space each step for speed [OK]

Common Mistakes:

• Thinking BST stores data randomly
• Confusing BST with hashing
• Assuming BST is a linked list

2. Which of the following is the correct property of a Binary Search Tree (BST)?

easy

A. Left child nodes are greater than the parent node

B. Left child nodes are smaller than the parent node

C. Right child nodes are smaller than the parent node

D. All child nodes have the same value as the parent node

Solution

1. Step 1: Recall BST node property

   In a BST, all nodes in the left subtree have values smaller than the parent node.

2. Step 2: Verify options

   Left child nodes are smaller than the parent node correctly states the left child nodes are smaller; others contradict BST rules.

3. Final Answer:

   Left child nodes are smaller than the parent node -> Option B

4. Quick Check:

   BST left < parent = true [OK]

Hint: Left child < parent, right child > parent [OK]

Common Mistakes:

• Mixing up left and right child values
• Assuming children equal parent
• Thinking left child is greater

3. Given the BST below, what is the result of searching for the value 7?

      10
     /  \
    5    15
   / \     \
  3   7     20

medium

A. Found at right child of 5

B. Found at left child of 5

C. Not found in the tree

D. Found at right child of 10

Solution

1. Step 1: Start search at root node 10

   Since 7 is less than 10, move to the left child node 5.

2. Step 2: Compare with node 5

   7 is greater than 5, so move to the right child of 5, which is 7.

3. Final Answer:

   Found at right child of 5 -> Option A

4. Quick Check:

   7 > 5, right child = 7 [OK]

Hint: Compare and move left or right until found [OK]

Common Mistakes:

• Stopping search too early
• Confusing left and right child directions
• Assuming 7 is right child of 10

4. Identify the error in this BST search pseudocode:

function searchBST(node, value):
  if node is null:
    return false
  if value == node.value:
    return true
  if value < node.value:
    return searchBST(node.right, value)
  else:
    return searchBST(node.left, value)

medium

A. It should search left subtree when value is less than node value

B. It should return true when node is null

C. It should compare value with node.left instead of node.value

D. It should always search both left and right subtrees

Solution

1. Step 1: Check direction of subtree search

   When value is less than node value, search should go to the left subtree, not right.

2. Step 2: Identify the incorrect recursive call

   The code incorrectly calls searchBST(node.right, value) for value < node.value, which is wrong.

3. Final Answer:

   It should search left subtree when value is less than node value -> Option A

4. Quick Check:

   Value < node.value -> search left [OK]

Hint: Less than -> left subtree, greater -> right subtree [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Returning true when node is null
• Searching both subtrees unnecessarily

5. Why does a balanced BST provide more efficient searching than an unbalanced BST?

hard

A. Because unbalanced BSTs do not follow BST rules

B. Because unbalanced BSTs store duplicate values

C. Because balanced BSTs use hashing internally

D. Because balanced BSTs minimize the tree height, reducing search steps

Solution

1. Step 1: Understand tree height impact on search

   Search time depends on tree height; shorter height means fewer steps to find a value.

2. Step 2: Compare balanced vs unbalanced BST

   Balanced BSTs keep height minimal (close to log n), while unbalanced BSTs can become like linked lists with height n.

3. Final Answer:

   Because balanced BSTs minimize the tree height, reducing search steps -> Option D

4. Quick Check:

   Balanced BST height low = faster search [OK]

Hint: Balanced tree = shorter height = faster search [OK]

Common Mistakes:

• Thinking unbalanced BSTs store duplicates
• Confusing BST with hashing
• Assuming unbalanced BSTs break BST rules