Searching in BST in Data Structures Theory - Step-by-Step Execution

Concept Flow - Searching in BST

Start at root node

↓

Compare target with current node value

↓

Found target, stop

↓

Go to left child

↓

Go to right child

↓

Is child node null?

Yes→Target not found, stop

No↓

Repeat comparison at new node

Start at the root and compare the target value with the current node. Move left if target is smaller, right if larger, until found or no child exists.

Execution Sample

Data Structures Theory

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)

This recursive function searches for a target value in a BST by comparing and moving left or right accordingly.

Analysis Table

Step	Current Node Value	Target	Comparison	Next Action	Result
1	15	13	13 < 15	Go to left child (10)	Continue
2	10	13	13 > 10	Go to right child (12)	Continue
3	12	13	13 > 12	Go to right child (14)	Continue
4	14	13	13 < 14	Go to left child (null)	Continue
5	null	13	Node is null	Target not found	Stop

💡 Reached a null child node without finding target; search ends with target not found.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
Current Node	15	10	12	14	null	null
Target	13	13	13	13	13	13
Result	Unknown	Unknown	Unknown	Unknown	Not Found	Not Found

Key Insights - 3 Insights

Why do we stop searching when we reach a null child node?

Because a null child means there is no further subtree to search, so the target cannot be in the BST. This is shown in execution_table step 5 where Current Node is null and search stops.

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

In a BST, all values in the left subtree are smaller than the current node. So if target < current node, we only need to search left subtree, as shown in step 1 where 13 < 15 leads to left child.

What happens if the target equals the current node value?

The search ends successfully because we found the target. This is the base case in the code and would appear as 'Found target, stop' in the concept_flow.

Visual Quiz - 3 Questions

Look at the execution_table, what is the Current Node value at Step 3?

A 14

B 12

C 10

D 15

💡 Hint

Check the 'Current Node Value' column in execution_table row for Step 3.

At which step does the search realize the target is not in the BST?

A Step 4

B Step 3

C Step 5

D Step 2

💡 Hint

Look for the step where 'Current Node' is null and the search stops in execution_table.

If the target was 14 instead of 13, at which step would the search find it?

A Step 4

B Step 3

C Step 5

D Step 2

💡 Hint

Consider the path taken and when the target equals the current node value.

Concept Snapshot

Searching in BST:
- Start at root node
- Compare target with current node value
- If equal, found target
- If target < node, go left
- If target > node, go right
- Stop if node is null (target not found)

Full Transcript

Searching in a Binary Search Tree (BST) starts at the root node. At each node, compare the target value with the node's value. If they are equal, the search ends successfully. If the target is smaller, move to the left child; if larger, move to the right child. This process repeats until the target is found or a null child is reached, which means the target is not in the tree. The example trace shows searching for 13 in a BST with nodes 15, 10, 12, and 14, ending when a null child is reached without finding 13.