BST Search Operation in DSA Javascript - Execution Trace

Concept Flow - BST Search Operation

Start at root node

↓

Compare target with current node value

↓

Target < current?

↓

Go left

↓

Is current null?

Yes→Not found, stop

No↓

Is current value == target?

Yes→Found, stop

↩Back to compare step

Start at the root and compare the target value with the current node. Move left if target is smaller, right if larger. Repeat until found or reach null.

Execution Sample

DSA Javascript

function searchBST(root, target) {
  let current = root;
  while (current !== null) {
    if (current.val === target) return current;
    current = target < current.val ? current.left : current.right;
  }
  return null;
}

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	8	target=5 < 8	Move left	8 / 3 10 / \ 1 6 14
2	Compare with 3	3	target=5 > 3	Move right	8 / 3 10 / \ 1 6 14
3	Compare with 6	6	target=5 < 6	Move left	8 / 3 10 / \ 1 6 14
4	Compare with null	null	Reached null	Stop	8 / 3 10 / \ 1 6 14
5	Result	null	Not found	Return null	8 / 3 10 / \ 1 6 14

💡 Reached null pointer at step 4, target not found in BST

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
current	8 (root)	3 (left child)	6 (right child of 3)	null (left child of 6)	null	null
target	5	5	5	5	5	5

Key Moments - 3 Insights

Why do we stop when current becomes null?

Because null means we reached a leaf's child without finding the target, so the target is not in the tree. See execution_table step 4.

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

In a BST, left children hold smaller values, so if target < current, we search left. See execution_table step 1 and 3.

What happens if the target equals the current node value?

We have found the target and stop searching immediately. This is shown in the code's if condition and would appear in execution if target was found.

Visual Quiz - 3 Questions

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

A 3

B 6

C null

D 8

💡 Hint

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

At which step does the search stop because it reached a null pointer?

A Step 3

B Step 4

C Step 5

D Step 2

💡 Hint

Look for the step where 'Current Node Value' is null and 'Pointer Change' says 'Stop' in execution_table.

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

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Check where the current node value equals the target in execution_table or code logic.

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.
- Stop if current is null (target not found).

Full Transcript

The BST search operation starts at the root node and compares the target value with the current node's value. If the target equals the current node's value, the search stops successfully. If the target is less, the search moves to the left child; if greater, to the right child. This process repeats until the target is found or the search reaches a null pointer, indicating the target is not in the tree. The execution table traces each step, showing the current node, comparison, pointer changes, and the visual state of the BST. Variables like 'current' update as the search moves through the tree. Key moments clarify why the search stops at null and why direction depends on comparison. The visual quiz tests understanding of pointer changes and stopping conditions.