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.