BST Search Operation in DSA Java - Execution Trace

Concept Flow - BST Search Operation

Start at root node

↓

Compare target with current node value

↓

Found: return node

↓

Go to left child

↓

Go to right child

↓

If child is null

→Not found: return null

Start at the root and compare the target value with the current node. Move left if smaller, right if larger, until found or no child exists.

Execution Sample

DSA Java

public TreeNode searchBST(TreeNode root, int target) {
    if (root == null || root.val == target) return root;
    if (target < root.val) return searchBST(root.left, target);
    else return searchBST(root.right, target);
}

Recursively search the BST for the target value, returning the node if found or null if not.

Execution Table

Step	Operation	Current Node Value	Comparison	Next Pointer	Visual State
1	Start at root	8	target=5 < 8	Go left	8 / 3 10 / \ 1 6 14
2	Move to left child	3	target=5 > 3	Go right	8 / 3 10 / \ 1 6 14
3	Move to right child	6	target=5 < 6	Go left	8 / 3 10 / \ 1 6 14
4	Move to left child	null	Reached null	Not found	8 / 3 10 / \ 1 6 14
5	Return	null	Target not found	Return null	8 / 3 10 / \ 1 6 14

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
currentNode	8	8	3	6	null	null
target	5	5	5	5	5	5
comparisonResult	N/A	5 < 8	5 > 3	5 < 6	Reached null	N/A

Key Moments - 3 Insights

Why do we stop searching when current node is null?

Because a null node 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 compare target with current node value at each step?

To decide whether to go left or right in the BST, since left children are smaller and right children are larger (see execution_table steps 1-3).

What happens if the target equals the current node value?

We return the current node immediately as the search is successful (not shown in this trace because target 5 is not in tree).

Visual Quiz - 3 Questions

Look at the execution_table, what is the currentNode value at step 3?

A 3

B 6

C null

D 8

💡 Hint

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

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

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'Reached null' in the 'Comparison' column 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 concept_flow).

Concept Snapshot

BST Search Operation:
- Start at root node
- Compare target with current node value
- If equal, return node
- If target < node, go left
- If target > node, go right
- Stop if node is null (not found)

Full Transcript

This visualization 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 are equal, we return the node immediately. If the target is smaller, we move to the left child; if larger, to the right child. We repeat this until we find the target or reach a null pointer, which means the target is not in the tree. The execution table tracks each step, showing the current node, comparison, and next pointer. The variable tracker shows how the current node and comparison results change. Key moments clarify why we stop at null and how comparisons guide the search. The quiz tests understanding of these steps and outcomes.

Practice

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

easy

A. To insert a new value into the BST

B. To find whether a given value exists in the BST

C. To delete a value from the BST

D. To traverse all nodes in the BST

Solution

1. Step 1: Understand the search operation

   The search operation checks if a specific value is present in the BST by comparing it with nodes.

2. Step 2: Differentiate from other operations

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

3. Final Answer:

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

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 Java method signature for a BST search function that returns a boolean indicating if a value exists?

easy

A. public boolean search(int value)

B. public void search(int value)

C. public int search(int value)

D. public String search(int value)

Solution

1. Step 1: Identify return type for search

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

2. Step 2: Check method signature correctness

   Method takes an int value to search and returns boolean. public boolean search(int value) matches this.

3. Final Answer:

   public boolean search(int value) -> Option A

4. Quick Check:

   Return type boolean for search [OK]

Hint: Search returns true/false, so use boolean return type [OK]

Common Mistakes:

• Using void return type for search
• Returning int or String instead of boolean
• Incorrect method parameter types

3. Consider the following BST and the search code snippet:

class Node {
  int data;
  Node left, right;
  Node(int d) { data = d; left = right = null; }
}

public boolean search(Node root, int key) {
  if (root == null) 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    15
//    / \     \
//   3   7     20

What is the output of search(root, 7)?

medium

A. null

B. false

C. true

D. Runtime error

Solution

1. Step 1: Trace search for key 7 starting at root 10

   7 < 10, so search left subtree (node 5).

2. Step 2: Trace search at node 5

   7 > 5, so search right subtree (node 7).

3. Step 3: Trace search at node 7

   Node data equals key (7), so return true.

4. Final Answer:

   true -> Option C

5. Quick Check:

   7 found in BST = true [OK]

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

Common Mistakes:

• Stopping search too early
• Confusing left and right subtree directions
• Assuming search returns node instead of boolean

4. The following Java method is intended to search a BST for a key. What is the bug?

public boolean search(Node root, int key) {
  if (root == null) 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. The recursive calls for left and right subtrees are swapped

B. The base case is missing

C. The method should return int instead of boolean

D. The method does not handle null keys

Solution

1. Step 1: Analyze recursive calls for BST search

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

2. Step 2: Identify swapped calls

   Code calls search(root.left, key) when key > root.data, which is incorrect; left and right calls are swapped.

3. Final Answer:

   The recursive calls for left and right subtrees are swapped -> Option A

4. Quick Check:

   Left/right calls must match key comparison [OK]

Hint: Left subtree for smaller keys, right for larger keys [OK]

Common Mistakes:

• Swapping left and right recursive calls
• Missing base case for null root
• Returning wrong data type

5. Given a BST with nodes inserted in this order: 15, 10, 20, 8, 12, 17, 25. Which sequence of nodes will the search operation visit when searching for 12?

hard

A. 10 -> 15 -> 12

B. 15 -> 20 -> 17 -> 12

C. 15 -> 10 -> 8 -> 12

D. 15 -> 10 -> 12

Solution

1. Step 1: Build BST structure from insertion order

   Insert 15 as root; 10 left of 15; 20 right of 15; 8 left of 10; 12 right of 10; 17 left of 20; 25 right of 20.

2. Step 2: Trace search path for key 12

   Start at 15: 12 < 15, go left to 10; 12 > 10, go right to 12; found key.

3. Final Answer:

   15 -> 10 -> 12 -> Option D

4. Quick Check:

   Search path follows BST rules [OK]

Hint: Follow left if smaller, right if larger until found [OK]

Common Mistakes:

• Visiting nodes not on search path
• Confusing insertion order with search path
• Assuming search visits all nodes