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.

Practice

1. What is the main advantage of searching in a Binary Search Tree (BST)?

easy

A. It allows faster search by using the order of elements

B. It stores elements in random order for quick access

C. It uses hashing to find elements instantly

D. It searches all nodes one by one sequentially

Solution

1. Step 1: Understand BST property

   A BST keeps elements ordered so smaller values are on the left and larger on the right.

2. Step 2: Use order for searching

   This order lets us decide to go left or right, skipping half the tree each step, making search faster.

3. Final Answer:

   It allows faster search by using the order of elements -> Option A

4. Quick Check:

   BST order speeds search = It allows faster search by using the order of elements [OK]

Hint: BST order guides search direction quickly [OK]

Common Mistakes:

• Thinking BST stores elements randomly
• Confusing BST with hashing
• Assuming linear search in BST

2. Which of the following is the correct way to decide the next node to visit when searching for a value in a BST?

easy

A. Go left if target is greater than current node

B. Go left if target is smaller than current node

C. Go right if target is smaller than current node

D. Always go to the root node

Solution

1. Step 1: Recall BST search rule

   If the target is smaller than the current node's value, we move to the left child.

2. Step 2: Apply rule to options

   Go left if target is smaller than current node correctly states to go left if target is smaller, which matches BST property.

3. Final Answer:

   Go left if target is smaller than current node -> Option B

4. Quick Check:

   Smaller target -> left child = Go left if target is smaller than current node [OK]

Hint: Smaller target means go left in BST [OK]

Common Mistakes:

• Reversing left and right directions
• Ignoring BST ordering rules
• Always going to root node

3. Consider the BST below:

      15
     /  \
    10  20
   /    / \
  8    17 25

Which nodes will be visited when searching for the value 17?

medium

A. [10, 8, 17]

B. [15, 10, 8]

C. [15, 20, 25]

D. [15, 20, 17]

Solution

1. Step 1: Start at root and compare with 17

   Root is 15. Since 17 > 15, move right to 20.

2. Step 2: Compare 20 with 17

   17 < 20, so move left to 17, which matches the target.

3. Final Answer:

   [15, 20, 17] -> Option D

4. Quick Check:

   Path to 17 = 15 -> 20 -> 17 [OK]

Hint: Follow BST rules: left if smaller, right if larger [OK]

Common Mistakes:

• Going left from 15 when target is larger
• Skipping nodes in path
• Confusing node values

4. You wrote code to search a BST but it always returns None even when the value exists. What is the most likely mistake?

medium

A. Not moving to left child when target is smaller

B. Using a queue instead of recursion

C. Always moving to left child regardless of target

D. Checking only the root node

Solution

1. Step 1: Understand BST search logic

   Search must move left if target is smaller, right if larger.

2. Step 2: Identify error in always moving left

   If code always moves left, it misses nodes on the right side where target might be.

3. Final Answer:

   Always moving to left child regardless of target -> Option C

4. Quick Check:

   Wrong direction causes search failure = Always moving to left child regardless of target [OK]

Hint: Move left or right based on comparison, not always left [OK]

Common Mistakes:

• Ignoring right subtree
• Checking only root node
• Using wrong data structure for traversal

5. Given a BST where some nodes have duplicate values on the right subtree, how should the search algorithm be adapted to find all occurrences of a target value?

hard

A. Traverse both left and right subtrees when node equals target

B. Search left subtree only once target is found

C. Stop search immediately after first match

D. Ignore duplicates and return first found

Solution

1. Step 1: Understand duplicates in BST

   Duplicates are stored in right subtree, so multiple matches can exist there.

2. Step 2: Adapt search to find all matches

   When a node equals target, search both left (for smaller) and right (for duplicates) subtrees to find all occurrences.

3. Final Answer:

   Traverse both left and right subtrees when node equals target -> Option A

4. Quick Check:

   Check both sides for duplicates = Traverse both left and right subtrees when node equals target [OK]

Hint: Check both subtrees when value matches to find duplicates [OK]

Common Mistakes:

• Stopping after first match
• Ignoring right subtree duplicates
• Searching only one subtree