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.

Practice

1. What is the main purpose of the search operation in a Binary Search Tree (BST)?

easy

A. To delete a value from the BST

B. To insert a new value into the BST

C. To find whether a given value exists in 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 designed to check if a specific value is present in the BST.

2. Step 2: Differentiate from other operations

   Insertion adds new values, deletion removes values, and traversal visits all nodes. Search only checks existence.

3. Final Answer:

   To find whether a given value exists in the BST -> Option C

4. Quick Check:

   Search = Find value presence [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert or delete
• Thinking search returns all nodes
• Assuming search modifies the tree

2. Which of the following is the correct TypeScript function signature for a BST search method that returns a boolean?

easy

A. function search(root: TreeNode | null, value: number): boolean

B. function search(value: number): TreeNode

C. function search(root: TreeNode, value: string): boolean

D. function search(root: TreeNode | null, value: number): void

Solution

1. Step 1: Analyze parameter types

   The search needs the root node (which can be null) and the value to find (a number).

2. Step 2: Analyze return type

   Search returns true or false, so return type should be boolean.

3. Final Answer:

   function search(root: TreeNode | null, value: number): boolean -> Option A

4. Quick Check:

   Correct params and boolean return [OK]

Hint: Search returns boolean, root can be null [OK]

Common Mistakes:

• Using wrong parameter types
• Returning void instead of boolean
• Using string instead of number for value

3. Given the BST below and the search function call search(root, 7), what will be the output?

BST structure:
10
/ \
5 15
/ \ \
3 7 20

Code snippet:

function search(root: TreeNode | null, value: number): boolean {
  if (!root) return false;
  if (root.val === value) return true;
  if (value < root.val) return search(root.left, value);
  return search(root.right, value);
}

console.log(search(root, 7));

medium

A. false

B. Error

C. undefined

D. true

Solution

1. Step 1: Trace search for value 7

   Start at root 10: 7 < 10, go left to 5. Then 7 > 5, go right to 7.

2. Step 2: Check node value

   Node value is 7, matches search value, so return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Found 7 in BST = true [OK]

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

Common Mistakes:

• Stopping search too early
• Confusing left and right child directions
• Returning false when node matches

4. The following TypeScript search function for a BST has a bug. What is the error?

function search(root: TreeNode | null, value: number): boolean {
  if (root === null) return false;
  if (root.val === value) return true;
  if (value > root.val) return search(root.left, value);
  else return search(root.right, value);
}

medium

A. The comparison operator should be >= instead of >

B. The recursive calls to left and right children are swapped

C. The function does not return a boolean

D. The base case is missing

Solution

1. Step 1: Check recursive calls logic

   For BST, if value > root.val, search should go right, but code goes left.

2. Step 2: Confirm swapped children calls

   Similarly, else goes right instead of left. So left and right calls are swapped.

3. Final Answer:

   The recursive calls to left and right children are swapped -> Option B

4. Quick Check:

   Left/right calls swapped = bug [OK]

Hint: Value > root goes right, not left [OK]

Common Mistakes:

• Mixing left and right child in recursion
• Ignoring base case (though present here)
• Wrong comparison operators

5. You want to search for a value in a BST that may contain duplicate values on the right subtree. Which modification to the standard BST search logic ensures you find the first occurrence of the value?

Choose the correct approach:

hard

A. Always search left subtree when value equals current node's value

B. Return true immediately when value equals current node's value

C. Search right subtree when value equals current node's value to find duplicates

D. Traverse entire tree inorder to find all occurrences

Solution

1. Step 1: Understand duplicate placement in BST

   Duplicates are stored in right subtree, so first occurrence is the leftmost matching node.

2. Step 2: Modify search to find first occurrence

   When value equals current node, continue searching left subtree to find earlier occurrence.

3. Final Answer:

   Always search left subtree when value equals current node's value -> Option A

4. Quick Check:

   Search left on equal to find first duplicate [OK]

Hint: On equal, go left to find first duplicate [OK]

Common Mistakes:

• Stopping search immediately on equal
• Searching right subtree on equal
• Doing full inorder traversal unnecessarily