BST Search Operation in DSA C

Mental Model

A binary search tree lets you find a value by comparing and moving left or right, skipping half the tree each time.

Analogy: Like looking for a word in a dictionary by opening near the middle and deciding to go left or right based on the word's first letter.

      5
     / \
    3   7
   / \   \
  2   4   8
↑ root

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, search for value 4

Goal: Find if value 4 exists in the BST and show the path taken

Step 1: Start at root node with value 5

5 [curr->5]

Why: We always start searching from the root of the BST

Step 2: Compare 4 with 5, move left because 4 < 5

5 -> 3 [curr->3]

Why: In BST, smaller values are on the left subtree

Step 3: Compare 4 with 3, move right because 4 > 3

5 -> 3 -> 4 [curr->4]

Why: In BST, larger values are on the right subtree

Step 4: Found node with value 4, stop search

5 -> 3 -> 4 [found]

Why: Search ends when the value is found

Result:

5 -> 3 -> 4 [found]

Annotated Code

DSA C

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

// Node structure for BST
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

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

// Insert value into BST
Node* insert(Node* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data); // go left
    } else if (data > root->data) {
        root->right = insert(root->right, data); // go right
    }
    return root;
}

// Search value in BST
Node* search(Node* root, int target) {
    if (root == NULL || root->data == target) {
        return root; // found or reached end
    }
    if (target < root->data) {
        return search(root->left, target); // search left
    } else {
        return search(root->right, target); // search right
    }
}

// Print BST inorder (for verification)
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    Node* root = NULL;
    int values[] = {5, 3, 7, 2, 4, 8};
    int n = sizeof(values) / sizeof(values[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }

    int target = 4;
    Node* found = search(root, target);
    if (found != NULL) {
        printf("Found %d in BST\n", target);
    } else {
        printf("%d not found in BST\n", target);
    }

    return 0;
}

if (root == NULL || root->data == target) {

stop search if node is null or value found

if (target < root->data) {

go left subtree if target smaller

return search(root->left, target);

recursive call to left child

return search(root->right, target);

recursive call to right child if target larger

Output

Found 4 in BST

Complexity Analysis

Time: O(h) where h is the height of the tree, because we follow one path down from root to leaf

Space: O(h) due to recursion stack in worst case equal to tree height

vs Alternative: Compared to linear search in an unsorted list O(n), BST search is faster if tree is balanced

Edge Cases

Empty BST

Search returns NULL immediately, meaning value not found

DSA C

if (root == NULL || root->data == target) {

Value not present in BST

Search reaches a NULL leaf and returns NULL

DSA C

if (root == NULL || root->data == target) {

Value is root node

Search returns root immediately without recursion

DSA C

if (root == NULL || root->data == target) {

When to Use This Pattern

When you need to quickly find if a value exists in a sorted tree structure, use BST search because it narrows down the search path by comparing values.

Common Mistakes

Mistake: Not checking if root is NULL before accessing data, causing crash
Fix: Always check if current node is NULL before comparing values

Summary

Searches for a value in a binary search tree by moving left or right based on comparisons.

Use when you have a sorted tree and want faster search than scanning all nodes.

The key is to compare and decide direction at each node, skipping half the tree each step.

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