BST Search Operation in DSA Typescript - Execution Trace

Concept Flow - BST Search Operation

Start at root node

↓

Compare target with current node value

↓

Found node, stop

↓

Go to left child

↓

Go to right child

↓

Is current node null?

Yes→Not found, stop

↩Back to compare step

Start at the root, compare target with current node, move left or right accordingly, repeat until found or null.

Execution Sample

DSA Typescript

function searchBST(root: TreeNode | null, target: number): TreeNode | null {
  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 nodes until found or end.

Execution Table

Step	Operation	Current Node Value	Comparison	Next Pointer	Visual State
1	Start at root	8	8 == 5? No	5 < 8 → go left	8 / \ 5 12 / \ \ 3 6 15
2	Move to left child	5	5 == 5? Yes	Found node	8 / \ 5* 12 / \ \ 3 6 15
3	Stop	5	Found target	N/A	8 / \ 5* 12 / \ \ 3 6 15

💡 Target 5 found at step 2, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
current	8 (root)	5 (left child of 8)	5 (found node)	5 (found node)
target	5	5	5	5

Key Moments - 3 Insights

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

Because in a BST, left child nodes hold smaller values. As shown in step 1 of execution_table, target 5 is less than 8, so we move left.

What happens if the target is not in the tree?

The search continues moving left or right until current becomes null, meaning no node matches target. This is shown by the exit condition in the concept_flow.

Why do we stop when current node value equals target?

Because we found the node containing the target value, so no further search is needed. This is shown in step 2 and 3 of execution_table.

Visual Quiz - 3 Questions

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

A 5

B 8

C 12

D 3

💡 Hint

Check the 'Current Node Value' column in execution_table row for step 2.

At which step does the search stop because the target is found?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Operation' and 'Comparison' columns in execution_table to find when target equals current node.

If the target was 10 instead of 5, which direction would the search go from the root node at step 1?

A Left

B Right

C Stay at root

D Stop immediately

💡 Hint

Refer to concept_flow and execution_table step 1: target < current goes left, target > current goes right.

Concept Snapshot

BST Search Operation:
- Start at root node
- Compare target with current node value
- If equal, return node
- If target < current, go left
- If target > current, go right
- Repeat until found or null

Full Transcript

This visual trace shows how to search a value in a Binary Search Tree (BST). We start at the root node and compare the target value with the current node's value. If they match, we stop and return the node. If the target is smaller, we move to the left child; if larger, to the right child. We repeat this process until we find the target or reach a null pointer, meaning the target is not in the tree. The execution table tracks each step, showing the current node, comparison, next pointer direction, and the tree's visual state. Variable tracking shows how the current node pointer changes during the search. Key moments clarify why we move left or right and when the search stops. The quiz tests understanding of these steps and decisions.