BST Search Operation in DSA C# - Execution Trace

Concept Flow - BST Search Operation

Start at root node

↓

Compare target with current node value

↓

Go left

↓

Is current null?

Yes→Target not found

No↓

Is current value == target?

Yes→Target found

↩Back to Compare step

Start at the root, compare the target with current node's value, go left if smaller, right if larger, repeat until found or null.

Execution Sample

DSA C#

Node current = root;
while (current != null) {
  if (current.value == target) return current;
  else if (target < current.value) current = current.left;
  else current = current.right;
}
return null;

Searches for a target value in a BST by traversing left or right depending on comparisons.

Execution Table

Step	Operation	Current Node Value	Comparison with Target	Pointer Changes	Visual State
1	Start at root	15	15 vs 10: 15 > 10	Move to left child	15 / 10 20
2	Compare current with target	10	10 vs 10: equal	Found target, stop	15 / 10 20
3	End	N/A	Target found	No change	15 / 10 20

💡 Target 10 found at step 2, search ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
current	15 (root)	10 (left child)	10 (found)	10 (found)
target	10	10	10	10

Key Moments - 3 Insights

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

Because in a BST, all left children have smaller values than the current node. See execution_table step 1 where 10 < 15 leads to moving left.

What happens if the target is not in the tree?

The search moves down the tree until current becomes null (no more nodes). Then it stops and returns null. 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 target value in the tree. See execution_table step 2 where comparison equals target and search ends.

Visual Quiz - 3 Questions

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

A 15

B 10

C 20

D null

💡 Hint

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

At which step does the search find the target value?

A Step 1

B Step 2

C Step 3

D Never

💡 Hint

Look at the 'Comparison with Target' and 'Operation' columns in execution_table.

If the target was 25, how would the pointer change at step 1?

A Move to left child

B Move to right child

C Stay at root

D Stop search

💡 Hint

Recall BST property: target > current node value means go right. See concept_flow arrows.

Concept Snapshot

BST Search Operation:
- Start at root node
- Compare target with current node
- If target < node, go left
- If target > node, go right
- Stop when found or reach null
- Returns node 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 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, meaning the target is not in the tree. The execution table tracks each step, showing the current node, comparison, pointer moves, and the tree's visual state. Key moments clarify why we move left or right and when the search stops. The quiz tests understanding of these steps. This method efficiently finds values by leveraging the BST's sorted structure.

Practice

1. What does the search operation in a Binary Search Tree (BST) do?

easy

A. Traverses all nodes in the BST

B. Deletes a node from the BST

C. Inserts a new node into the BST

D. Finds whether a given value exists in the BST

Solution

1. Step 1: Understand the purpose of BST search

   The search operation checks if a specific value is present in the BST by comparing values starting from the root.

2. Step 2: Differentiate from other operations

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

3. Final Answer:

   Finds whether a given value exists in the BST -> Option D

4. Quick Check:

   Search = Find value [OK]

Hint: Search checks presence, not insert or delete [OK]

Common Mistakes:

• Confusing search with insertion
• Thinking search deletes nodes
• Assuming search visits all nodes

2. Which of the following is the correct C# syntax to start searching for a value in a BST with root node root and target value key?

easy

A. bool found = root.Search(key);

B. bool found = Search(root, key);

C. bool found = root.search(key);

D. bool found = Search(key, root);

Solution

1. Step 1: Understand typical BST search method signature

   Usually, search is a static or instance method taking the root node and key as parameters, like Search(root, key).

2. Step 2: Analyze options for correct syntax

   bool found = Search(root, key); matches the common pattern. bool found = root.Search(key); assumes Search is an instance method on root, which may not exist. bool found = root.search(key); uses lowercase 'search' which is not standard C# naming. bool found = Search(key, root); has parameters reversed.

3. Final Answer:

   bool found = Search(root, key); -> Option B

4. Quick Check:

   Search(root, key) is standard call [OK]

Hint: Search usually takes root and key as parameters [OK]

Common Mistakes:

• Using lowercase method names in C#
• Reversing parameter order
• Assuming search is a method on node instance

3. Consider the following C# code for searching a BST:

class Node {
  public int val;
  public Node left, right;
  public Node(int v) { val = v; left = right = null; }
}

bool Search(Node root, int key) {
  if (root == null) return false;
  if (root.val == key) return true;
  if (key < root.val) return Search(root.left, key);
  else return Search(root.right, key);
}

// BST structure:
//       10
//      /  \
//     5   15
//    /    / \
//   2    12 20

Node root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(2);
root.right.left = new Node(12);
root.right.right = new Node(20);

Console.WriteLine(Search(root, 12));
Console.WriteLine(Search(root, 7));

What is the output?

medium

A. True\nFalse

B. False\nTrue

C. True\nTrue

D. False\nFalse

Solution

1. Step 1: Trace Search(root, 12)

   Start at root 10: 12 > 10, go right to 15. 12 < 15, go left to 12. Found 12, return true.

2. Step 2: Trace Search(root, 7)

   Start at root 10: 7 < 10, go left to 5. 7 > 5, go right which is null. Return false.

3. Final Answer:

   True False -> Option A

4. Quick Check:

   12 found = True, 7 not found = False [OK]

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

Common Mistakes:

• Confusing left and right child directions
• Assuming 7 is in the tree
• Not returning false on null node

4. The following C# code attempts to search a BST but has a bug:

bool Search(Node root, int key) {
  if (root == null) return false;
  if (root.val == key) return true;
  if (key > root.val) return Search(root.left, key);
  else return Search(root.right, key);
}

What is the bug in this code?

medium

A. It searches left subtree when key is greater than root value

B. It returns true when root is null

C. It does not check if root value equals key

D. It does not handle duplicate keys

Solution

1. Step 1: Analyze the direction of subtree search

   When key > root.val, the search should go to the right subtree, but code incorrectly goes left.

2. Step 2: Confirm other conditions are correct

   Code correctly returns false if root is null and checks equality properly.

3. Final Answer:

   It searches left subtree when key is greater than root value -> Option A

4. Quick Check:

   Greater key goes right, not left [OK]

Hint: Greater keys go right subtree, smaller go left [OK]

Common Mistakes:

• Swapping left and right subtree in conditions
• Missing null check
• Ignoring equality check

5. You have a BST with nodes inserted in this order: 8, 3, 10, 1, 6, 14, 4, 7, 13. You want to search for the value 7. Which sequence of nodes will the search visit?

hard

A. 8 -> 3 -> 4 -> 7

B. 8 -> 10 -> 14 -> 7

C. 8 -> 3 -> 6 -> 7

D. 8 -> 6 -> 7

Solution

1. Step 1: Build the BST structure mentally

   Insert 8 as root. 3 left of 8. 10 right of 8. 1 left of 3. 6 right of 3. 14 right of 10. 4 left of 6. 7 right of 6. 13 left of 14.

2. Step 2: Trace search for 7

   Start at 8: 7 < 8 go left to 3. 7 > 3 go right to 6. 7 > 6 go right to 7. Found 7.

3. Final Answer:

   8 -> 3 -> 6 -> 7 -> Option C

4. Quick Check:

   Search path follows BST rules [OK]

Hint: Compare key at each node, go left if smaller, right if larger [OK]

Common Mistakes:

• Skipping nodes in path
• Going left when should go right
• Confusing insertion order with search path