BST Search Operation in DSA Python - Execution Trace

Concept Flow - BST Search Operation

Start at root node

↓

Is current node null?

Yes→Not found, stop

No↓

Compare target with current node value

↓

Go left

↓

Repeat from current node

↓

Found target, stop

Start at the root and compare the target with the current node's value. If equal, found it. If less, go left. If more, go right. Repeat until found or reach null.

Execution Sample

DSA Python

def bst_search(root, target):
    current = root
    while current:
        if current.val == target:
            return True
        elif target < current.val:
            current = current.left
        else:
            current = current.right
    return False

Searches for a target value in a BST by traversing left or right based on comparisons.

Execution Table

Step	Operation	Current Node Value	Comparison	Pointer Change	Visual State
1	Start at root	10	target=7 < 10	Move to left child	10 / 5 15
2	At node 5	5	target=7 > 5	Move to right child	10 / 5 15 \ 7
3	At node 7	7	target=7 == 7	Found target	10 / 5 15 \ 7
4	Stop	7	Found target	No change	10 / 5 15 \ 7

💡 Target 7 found at node with value 7, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current	root (10)	5	7	7	7
target	7	7	7	7	7

Key Moments - 3 Insights

Why do we move left when target is less than current node value?

Because in a BST, all left children have smaller values than the current node. See execution_table step 1 where target 7 < 10 leads to moving left.

What happens if the target is not in the tree?

The search moves down the tree until current becomes null (no child), then stops and returns False. This is not shown here but would be a step where current is None.

Why do we stop when current node value equals target?

Because we found the target value in the tree, so no need to continue. See execution_table step 3 where comparison is equal and search stops.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 2?

A 7

B 5

C 10

D 15

💡 Hint

Check the 'Pointer Change' and 'Current Node Value' columns at step 2.

At which step does the search find the target value?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look for the step where 'Comparison' shows equality and 'Operation' says 'Found target'.

If the target was 20, which direction would the search move from the root node?

A Left

B Stay at root

C Right

D Stop immediately

💡 Hint

Recall BST property: target > current node value means move right.

Concept Snapshot

BST Search Operation:
- Start at root node
- Compare target with current node value
- If equal, found target
- If target < current, go left
- If target > current, go right
- Repeat until found or reach null

Full Transcript

The BST search operation starts at the root node. At each step, it compares the target value with the current node's value. If they are equal, the search stops successfully. If the target is less, the search moves to the left child; if more, it moves to the right child. This process repeats until the target is found or the search reaches a null pointer, meaning the target is not in the tree. The execution table shows a search for target 7 in a BST with root 10, moving left to 5, then right to 7, where it finds the target and stops.

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