Why BST Search Operation in DSA C?

The Big Idea

What if you could find any name in a huge list in just a few steps instead of checking one by one?

The Scenario

Imagine you have a big phone book with thousands of names, and you want to find one person's phone number. If you look at each name one by one from the start, it will take a very long time.

The Problem

Searching manually through a list means checking every single entry until you find the right one. This is slow and tiring, especially if the list is very long. You can easily lose your place or make mistakes.

The Solution

A Binary Search Tree (BST) organizes data so you can quickly jump to the part where your item should be. Instead of checking every entry, you compare and decide to go left or right, cutting the search time drastically.

Before vs After

✗ Before

for (int i = 0; i < size; i++) {
    if (array[i] == target) {
        return i;
    }
}
return -1;

✓ After

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

What It Enables

This operation lets you find any item in a sorted tree quickly, even if the tree has thousands of items.

Real Life Example

When you search for a contact on your phone, the phone uses a method like BST search to find the contact fast without scrolling through the entire list.

Key Takeaways

Manual search checks every item, which is slow.

BST search uses comparisons to jump left or right, speeding up search.

BST search works best when data is organized in a tree structure.

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