BST Search Operation in DSA C++ - Execution Trace

Concept Flow - BST Search Operation

Start at root node

↓

Compare target with current node

↓

Go left

↓

Is current node null?

↓

Not found

↓

Done

Start at the root, compare target with current node, go left if smaller, right if larger, repeat until found or null.

Execution Sample

DSA C++

struct Node {
  int val;
  Node* left;
  Node* right;
};

bool searchBST(Node* root, int target) {
  while (root != nullptr) {
    if (root->val == target) return true;
    root = (target < root->val) ? root->left : root->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 with Target	Pointer Change	Visual State
1	Start at root	8	8 vs 5: 5 < 8, go left	Move to left child	8 / \ 3 10 / \ 1 6 14
2	Compare with 3	3	3 vs 5: 5 > 3, go right	Move to right child	8 / \ 3 10 / \ 1 6 14
3	Compare with 6	6	6 vs 5: 5 < 6, go left	Move to left child	8 / \ 3 10 / \ 1 6 14
4	Compare with null	null	Reached null, target not found	Stop	8 / \ 3 10 / \ 1 6 14
5	Exit	null	Target 5 not found in BST	None	8 / \ 3 10 / \ 1 6 14

💡 Reached null pointer, target 5 not found in BST

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
root	Node(8)	Node(3)	Node(6)	null	null	null
current node value	8	3	6	null	null	null

Key Moments - 3 Insights

Why do we stop when current node becomes null?

Because null means we reached a leaf's child without finding the target, so the target is not in the BST (see execution_table step 4).

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

In BST, left child nodes hold smaller values, so if target < current node, we search left (see execution_table step 1).

What if the target equals the current node value?

We stop and return true immediately because we found the target (not shown in this trace but would happen if root->val == target).

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node value at step 3?

A 3

B 6

C 8

D null

💡 Hint

Check the 'Current Node Value' column at step 3 in execution_table.

At which step does the search reach a null pointer indicating target not found?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'null' in 'Current Node Value' and 'Pointer Change' columns in execution_table.

If the target was 6 instead of 5, at which step would the search stop?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

If target equals current node value, search stops immediately (see key_moments about equality).

Concept Snapshot

BST Search Operation:
- Start at root node
- Compare target with current node value
- If target < node, go left
- If target > node, go right
- Repeat until found or reach null (not found)
- Returns true if found, false otherwise

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 the target is smaller, it moves to the left child; if larger, it moves to the right child. This process repeats until the target is found or a null pointer is reached, indicating the target is not in the tree. The execution table shows each step's current node, comparison, pointer changes, and the tree's visual state. Key moments clarify why traversal stops at null and how decisions to go left or right are made. The visual quiz tests understanding of node values at steps and stopping conditions. The snapshot summarizes the search logic in a few lines.

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 node in the BST

C. To delete a node 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 nodes, deletion removes nodes, traversal visits nodes. Search only checks presence.

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 insertion
• Thinking search modifies the tree
• Mixing search with traversal

2. Which of the following is the correct syntax to start a recursive search function in C++ for a BST node pointer root and integer key?

easy

A. void search(Node root, int key) { ... }

B. bool search(Node* root, int key) { ... }

C. int search(Node* root, int key) { ... }

D. Node search(Node* root, int key) { ... }

Solution

1. Step 1: Identify return type for search

   Search returns true/false if key found, so return type should be bool.

2. Step 2: Check parameter types

   Root is a pointer to Node, key is int. So signature is bool search(Node* root, int key).

3. Final Answer:

   bool search(Node* root, int key) { ... } -> Option B

4. Quick Check:

   Return bool and pointer param [OK]

Hint: Search returns bool, takes Node pointer and key [OK]

Common Mistakes:

• Using void return type for search
• Passing Node by value instead of pointer
• Returning Node instead of bool

3. Consider the following BST and the search function call search(root, 15). What will be the output?

struct Node {
  int data;
  Node* left;
  Node* right;
};

bool search(Node* root, int key) {
  if (!root) return false;
  if (root->data == key) return true;
  if (key < root->data) return search(root->left, key);
  else return search(root->right, key);
}

// BST structure:
//       10
//      /  \
//     5    20
//         /  \
//        15  30

// Call:
// bool found = search(root, 15);
// std::cout << (found ? "Found" : "Not Found");

medium

A. Found

B. Not Found

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Trace search path for key 15

   Start at root 10, 15 > 10, go right to 20. Then 15 < 20, go left to 15.

2. Step 2: Check node data at 15

   Node data matches key 15, so function returns true and prints "Found".

3. Final Answer:

   Found -> Option A

4. Quick Check:

   Key found in BST = Found [OK]

Hint: Follow BST rules left/right to find key [OK]

Common Mistakes:

• Stopping search too early
• Confusing left and right child directions
• Assuming key not found when present

4. Identify the error in the following BST search function and choose the correct fix:

bool search(Node* root, int key) {
  if (root == nullptr) return false;
  if (root->data == key) return true;
  if (key > root->data) return search(root->left, key);
  else return search(root->right, key);
}

medium

A. Remove base case for nullptr

B. Change return type to int

C. Swap left and right in recursive calls; should be key < root->data for left

D. Add print statements for debugging

Solution

1. Step 1: Analyze recursive calls logic

   For BST, if key < root->data, search left; if key > root->data, search right.

2. Step 2: Identify incorrect direction

   Code searches left when key > root->data, which is wrong. Left subtree has smaller values.

3. Step 3: Correct the recursive calls

   Swap left and right calls: if (key < root->data) search left; else search right.

4. Final Answer:

   Swap left and right in recursive calls; should be key < root->data for left -> Option C

5. Quick Check:

   BST property fixes search direction [OK]

Hint: Left subtree < node, right subtree > node [OK]

Common Mistakes:

• Mixing left and right subtree directions
• Ignoring base case
• Changing return type unnecessarily

5. Given a BST with nodes inserted in this order: 25, 15, 50, 10, 22, 35, 70. You want to search for the value 22. How many nodes will the search function visit before finding 22?

hard

A. 2

B. 5

C. 4

D. 3

Solution

1. Step 1: Build BST structure from insertion order

   Insert 25 (root), then 15 (left of 25), 50 (right of 25), 10 (left of 15), 22 (right of 15), 35 (left of 50), 70 (right of 50).

2. Step 2: Trace search path for 22

   Start at 25 (visit 1), 22 < 25 go left to 15 (visit 2), 22 > 15 go right to 22 (visit 3), found key.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Nodes visited = 3 [OK]

Hint: Count nodes visited following BST search path [OK]

Common Mistakes:

• Counting nodes not visited
• Misplacing nodes in BST
• Stopping count before finding key