BST Search Operation in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to compare the current node's value with the target key.

DSA C

if (root->data [1] key) {
    return root;
}

Drag options to blanks, or click blank then click option'

A!=

B<

C>

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' or '>' instead of '==' causes wrong comparisons.

Using '!=' will never find the exact match.

The search checks if the current node's data is equal to the key.

2fill in blank

medium

Complete the code to decide to search in the left subtree if the key is smaller.

DSA C

if (key [1] root->data) {
    return searchBST(root->left, key);
}

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' will search the wrong subtree.

Using '==' or '!=' here is incorrect.

If the key is less than the current node's data, search the left subtree.

3fill in blank

hard

Fix the error in the recursive call to search the right subtree when key is greater.

DSA C

if (key [1] root->data) {
    return searchBST(root->right, key);
}

Drag options to blanks, or click blank then click option'

A>

B!=

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' will search the wrong subtree.

Using '==' or '!=' here is incorrect.

If the key is greater than the current node's data, search the right subtree.

4fill in blank

hard

Fill both blanks to complete the base case and recursive search logic.

DSA C

if (root == NULL) {
    return [1];
}

if (key == root->data) {
    return root;
} else if (key [2] root->data) {
    return searchBST(root->left, key);
} else {
    return searchBST(root->right, key);
}

Drag options to blanks, or click blank then click option'

ANULL

Broot

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Returning root instead of NULL in base case.

Using '>' instead of '<' for left subtree condition.

Return NULL if node is not found. Use '<' to decide left subtree search.

5fill in blank

hard

Fill all three blanks to complete the BST search function.

DSA C

struct Node* searchBST(struct Node* root, int key) {
    if (root == [1]) {
        return [2];
    }
    if (key == root->data) {
        return root;
    } else if (key [3] root->data) {
        return searchBST(root->left, key);
    } else {
        return searchBST(root->right, key);
    }
}

Drag options to blanks, or click blank then click option'

ANULL

Broot

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Returning root instead of NULL in base case.

Using '>' instead of '<' for left subtree condition.

Check if root is NULL, return NULL. Use '<' to search left subtree.

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