BST Search Operation in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Search Function

What is the output of the following C code that searches for a value in a Binary Search Tree (BST)?

DSA C

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

Node* search(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);
    }
}

#include <stdio.h>
#include <stdlib.h>

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    Node* root = newNode(10);
    root->left = newNode(5);
    root->right = newNode(15);
    root->left->left = newNode(3);
    root->left->right = newNode(7);

    Node* result = search(root, 7);
    if (result != NULL) {
        printf("Found: %d\n", result->data);
    } else {
        printf("Not Found\n");
    }
    return 0;
}

A Found: 7

B Found: 5

C Not Found

D Found: 10

💡 Hint

Trace the search path comparing the key with node values.

The search starts at root (10). Since 7 < 10, it goes left to 5. Then 7 > 5, it goes right to 7. It finds the node with data 7 and returns it.

❓ Predict Output

intermediate

Result of Searching a Non-Existent Value in BST

What will be printed when searching for a value not present in the BST?

DSA C

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

Node* search(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);
    }
}

#include <stdio.h>
#include <stdlib.h>

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    Node* root = newNode(20);
    root->left = newNode(10);
    root->right = newNode(30);
    root->left->left = newNode(5);
    root->left->right = newNode(15);

    Node* result = search(root, 25);
    if (result != NULL) {
        printf("Found: %d\n", result->data);
    } else {
        printf("Not Found\n");
    }
    return 0;
}

A Not Found

B Found: 20

C Found: 30

D Found: 25

💡 Hint

The value 25 is not in the tree; what does the search return when it reaches a NULL node?

The search goes right from 20 to 30, then left (NULL) because 25 < 30. It returns NULL, so 'Not Found' is printed.

🔧 Debug

advanced

Identify the Bug in BST Search Function

What error will occur when running this BST search function code?

DSA C

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

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

#include <stdio.h>
#include <stdlib.h>

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    Node* root = newNode(8);
    root->left = newNode(3);
    root->right = newNode(10);

    Node* result = search(root, 10);
    if (result != NULL) {
        printf("Found: %d\n", result->data);
    } else {
        printf("Not Found\n");
    }
    return 0;
}

A Compilation error due to missing semicolon

B Correct output: Found: 10

C Infinite recursion causing stack overflow

D Incorrect output due to wrong subtree traversal

💡 Hint

Check the direction of recursive calls for key comparison.

The code incorrectly calls search on root->left when key > root->data, but it should go right. This causes wrong traversal leading to incorrect output ("Not Found" instead of "Found: 10").

❓ Predict Output

advanced

Output of Iterative BST Search

What will be printed by this iterative BST search code when searching for 12?

DSA C

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

Node* searchIterative(Node* root, int key) {
    while (root != NULL) {
        if (root->data == key) {
            return root;
        } else if (key < root->data) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return NULL;
}

#include <stdio.h>
#include <stdlib.h>

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    Node* root = newNode(15);
    root->left = newNode(10);
    root->right = newNode(20);
    root->left->left = newNode(8);
    root->left->right = newNode(12);

    Node* result = searchIterative(root, 12);
    if (result != NULL) {
        printf("Found: %d\n", result->data);
    } else {
        printf("Not Found\n");
    }
    return 0;
}

A Not Found

B Found: 12

C Found: 10

D Found: 15

💡 Hint

Follow the while loop and check the node values compared to 12.

The search starts at 15, goes left to 10 (since 12 < 15), then right to 12 (since 12 > 10), finds the node and returns it.

🧠 Conceptual

expert

Number of Nodes Visited in Worst Case BST Search

In a BST with n nodes arranged like a linked list (all nodes have only right child), what is the maximum number of nodes visited when searching for a value not present in the tree?

A n/2

B log2(n)

C n

D 1

💡 Hint

Think about the shape of the tree and how search proceeds.

When the BST is skewed like a linked list, searching for a missing value requires visiting all nodes from root to the last node, so n nodes are visited.

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