BST Search Operation in DSA C - Execution Trace

Concept Flow - BST Search Operation

Start at root node

↓

Compare target with current node

↓

Go left

↓

Node is null?

Yes→Not found

No↓

Node value == target?

Yes→Found

↩Back to Compare step

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

Execution Sample

DSA C

struct Node {
  int val;
  struct Node* left;
  struct Node* right;
};

struct Node* search(struct Node* root, int target) {
  if (!root || root->val == target) return root;
  if (target < root->val) return search(root->left, target);
  else return search(root->right, target);
}

Recursive search in BST returns node with target value or NULL if not found.

Execution Table

Step	Operation	Current Node Value	Comparison with Target	Next Pointer	Visual State
1	Start at root	15	15 vs 10: 15 > 10	Go left	15 / 10 20 / 8 12
2	Move to left child	10	10 vs 10: equal	Found	15 / 10 20 / 8 12
3	Return node	10	Match found	Stop	15 / 10 20 / 8 12

💡 Search stops when node value equals target (10) at step 2.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
current_node	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, left child nodes hold smaller values. See execution_table step 1 where 10 < 15 leads to going left.

What happens if the target is not in the tree?

The search moves down until it reaches a null pointer (no child), then returns NULL. This is shown by the exit condition in concept_flow.

Why do we stop when current node value equals target?

Because we found the node containing the target value, so no need to search further. See execution_table step 2.

Visual Quiz - 3 Questions

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

A 15

B 10

C 20

D 8

💡 Hint

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

At which step does the search find the target node?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look for 'Match found' in the 'Comparison with Target' column in execution_table.

If the target was 25, which direction would the search go from the root node at step 1?

A Go left

B Go right

C Stop, found

D Return NULL immediately

💡 Hint

Compare target 25 with root 15 in execution_table step 1 logic.

Concept Snapshot

BST Search Operation:
- Start at root node
- Compare target with current node value
- If target < node, go left
- If target > node, go right
- Repeat until found or reach null
- Returns node or NULL if not found

Full Transcript

The BST search operation starts at the root node. At each step, it compares the target value with the current node's value. If the target is smaller, it moves to the left child; if larger, it moves to the right child. This continues until the target is found or a null pointer is reached, indicating the target is not in the tree. The execution table shows a search for 10 starting at root 15, moving left to 10, and finding the target. Variables track the current node and target values at each step. Key moments clarify why the search moves left or right and when it stops. The visual quiz tests understanding of node values and directions during search.

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 find whether a given value exists in the BST

C. To insert a new value into 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 values starting from the root.

2. Step 2: Differentiate from other operations

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

3. Final Answer:

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

4. Quick Check:

   Search = Find value [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 C syntax to start searching for a value in a BST given a pointer root and an integer key?

easy

A. search(root, key);

B. search(key, root);

C. search(root->key, key);

D. search(key);

Solution

1. Step 1: Understand function parameters for BST search

   The search function typically takes the root node pointer first, then the key to find.

2. Step 2: Check each option's parameter order and types

   search(root, key); correctly passes root and key. search(key, root); reverses parameters. search(root->key, key); passes a value, not a node pointer. search(key); misses root.

3. Final Answer:

   search(root, key); -> Option A

4. Quick Check:

   Function(root, key) = Correct call [OK]

Hint: Root pointer first, key second in search call [OK]

Common Mistakes:

• Swapping parameter order
• Passing node value instead of pointer
• Omitting root parameter

3. Consider the following BST and the search function call search(root, 15);. What will be the output if the BST contains nodes with values 10, 5, 15, 12, 20?

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

struct Node* search(struct Node* root, int key) {
  if (root == NULL || root->data == key)
    return root;
  if (key < root->data)
    return search(root->left, key);
  else
    return search(root->right, key);
}

// Assume root points to the BST described above
struct Node* result = search(root, 15);
if (result != NULL) printf("Found: %d", result->data);
else printf("Not Found");

medium

A. Found: 20

B. Found: 10

C. Not Found

D. Found: 15

Solution

1. Step 1: Trace the search for key 15 in the BST

   Start at root (10). Since 15 > 10, go right to node 15.

2. Step 2: Check if node 15 matches key

   Node 15's data equals key 15, so return this node.

3. Final Answer:

   Found: 15 -> Option D

4. Quick Check:

   Search found node with data 15 [OK]

Hint: Compare key with node, go left or right accordingly [OK]

Common Mistakes:

• Stopping at root without checking children
• Returning wrong node data
• Assuming search always returns root

4. The following C code attempts to search for a key in a BST but has a bug. What is the error?

struct Node* search(struct Node* root, int key) {
  if (root == NULL) 
    return NULL;
  if (root->data == key)
    return root;
  if (key > root->data)
    return search(root->left, key);
  else
    return search(root->right, key);
}

medium

A. Missing base case for empty tree

B. Incorrect return type for search function

C. The recursive calls for left and right subtrees are swapped

D. No error, code is correct

Solution

1. Step 1: Analyze recursive calls for BST search

   For BST, if key > root->data, search right subtree; if less, search left subtree.

2. Step 2: Check the code's recursive calls

   Code calls search(root->left, key) when key > root->data, which is incorrect. It should call search(root->right, key).

3. Final Answer:

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

4. Quick Check:

   Key > root means go right, not left [OK]

Hint: Go right if key > node, left if less [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Ignoring base case
• Confusing comparison operators

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

hard

A. 8 -> 10 -> 14 -> 13

B. 8 -> 3 -> 6 -> 7 -> 13

C. 8 -> 10 -> 13

D. 8 -> 14 -> 13

Solution

1. Step 1: Start at root and compare with key 13

   Root is 8. Since 13 > 8, go right to 10.

2. Step 2: Compare 13 with 10 and move accordingly

   13 > 10, go right to 14. Then 13 < 14, go left to 13.

3. Step 3: Sequence of visited nodes

   Visited nodes are 8, 10, 14, then 13.

4. Final Answer:

   8 -> 10 -> 14 -> 13 -> Option A

5. Quick Check:

   Follow BST rules to trace path [OK]

Hint: Compare and move left or right until found [OK]

Common Mistakes:

• Skipping nodes in path
• Going left when should go right
• Assuming direct jump to node