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.

      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13

↑ root

Dry Run Walkthrough

Input: BST: 8->3->10->1->6->14->4->7->13, search value 7

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

Step 1: Start at root node 8

8 [curr->8] -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13

Why: We always start searching from the root

Step 2: Compare 7 with 8, 7 < 8, move to left child 3

8 -> 3 [curr->3] -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13

Why: In BST, smaller values are on the left

Step 3: Compare 7 with 3, 7 > 3, move to right child 6

8 -> 3 -> 6 [curr->6] -> 10 -> 1 -> 14 -> 4 -> 7 -> 13

Why: In BST, larger values are on the right

Step 4: Compare 7 with 6, 7 > 6, move to right child 7

8 -> 3 -> 6 -> 7 [curr->7] -> 10 -> 1 -> 14 -> 4 -> 13

Why: Continue moving right for larger values

Step 5: Compare 7 with 7, found the value

8 -> 3 -> 6 -> 7 [found]

Why: Value matches current node, search ends

Result:

8 -> 3 -> 6 -> 7 found

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Insert helper to build tree for testing
Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

// Search function returns true if val found
bool searchBST(Node* root, int val) {
    Node* curr = root;
    while (curr) {
        if (val == curr->val) return true; // found value
        else if (val < curr->val) curr = curr->left; // go left
        else curr = curr->right; // go right
    }
    return false; // not found
}

int main() {
    Node* root = nullptr;
    int values[] = {8,3,10,1,6,14,4,7,13};
    for (int v : values) root = insert(root, v);

    int target = 7;
    bool found = searchBST(root, target);
    cout << (found ? "7 found" : "7 not found") << endl;
    return 0;
}

Node* curr = root;

start searching from root node

while (curr) {

continue until we reach a null pointer or find value

if (val == curr->val) return true;

check if current node has the target value

else if (val < curr->val) curr = curr->left;

move left if target is smaller

else curr = curr->right;

move right if target is larger

Output

7 found

Complexity Analysis

Time: O(h) where h is the height of the tree, because we move down one level each step

Space: O(1) because we use only a few pointers and no extra data structures

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

Edge Cases

Empty tree

Search returns false immediately

DSA C++

while (curr) {

Value not present in tree

Search moves down until null and returns false

DSA C++

while (curr) {

Value is root node

Search finds value immediately and returns true

DSA C++

if (val == curr->val) return true;

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 skips half the nodes each step.

Common Mistakes

Mistake: Not moving left or right correctly based on comparison
Fix: Always compare target with current node and move left if smaller, right if larger

Mistake: Forgetting to check if current node is null before accessing
Fix: Use a loop condition that stops when current node is null

Summary

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

Use when you want fast lookup in a sorted tree structure.

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

Practice

1. What is the main purpose of the search operation in a Binary Search Tree (BST)?

easy

A. To find whether a given value exists in the BST

B. To insert a new node in the BST

C. To delete a node from the BST

D. To traverse all nodes in the BST

Solution

1. Step 1: Understand the purpose of search in BST

   The search operation is used to check if a specific value is present in the BST.

2. Step 2: Differentiate from other operations

   Insertion adds nodes, deletion removes nodes, traversal visits nodes. Search only checks presence.

3. Final Answer:

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

4. Quick Check:

   Search = Find value [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insertion
• Thinking search modifies the tree
• Mixing search with traversal

2. Which of the following is the correct syntax to start a recursive search function in C++ for a BST node pointer root and integer key?

easy

A. void search(Node root, int key) { ... }

B. bool search(Node* root, int key) { ... }

C. int search(Node* root, int key) { ... }

D. Node search(Node* root, int key) { ... }

Solution

1. Step 1: Identify return type for search

   Search returns true/false if key found, so return type should be bool.

2. Step 2: Check parameter types

   Root is a pointer to Node, key is int. So signature is bool search(Node* root, int key).

3. Final Answer:

   bool search(Node* root, int key) { ... } -> Option B

4. Quick Check:

   Return bool and pointer param [OK]

Hint: Search returns bool, takes Node pointer and key [OK]

Common Mistakes:

• Using void return type for search
• Passing Node by value instead of pointer
• Returning Node instead of bool

3. Consider the following BST and the search function call search(root, 15). What will be the output?

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

bool search(Node* root, int key) {
  if (!root) return false;
  if (root->data == key) return true;
  if (key < root->data) return search(root->left, key);
  else return search(root->right, key);
}

// BST structure:
//       10
//      /  \
//     5    20
//         /  \
//        15  30

// Call:
// bool found = search(root, 15);
// std::cout << (found ? "Found" : "Not Found");

medium

A. Found

B. Not Found

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Trace search path for key 15

   Start at root 10, 15 > 10, go right to 20. Then 15 < 20, go left to 15.

2. Step 2: Check node data at 15

   Node data matches key 15, so function returns true and prints "Found".

3. Final Answer:

   Found -> Option A

4. Quick Check:

   Key found in BST = Found [OK]

Hint: Follow BST rules left/right to find key [OK]

Common Mistakes:

• Stopping search too early
• Confusing left and right child directions
• Assuming key not found when present

4. Identify the error in the following BST search function and choose the correct fix:

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

medium

A. Remove base case for nullptr

B. Change return type to int

C. Swap left and right in recursive calls; should be key < root->data for left

D. Add print statements for debugging

Solution

1. Step 1: Analyze recursive calls logic

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

2. Step 2: Identify incorrect direction

   Code searches left when key > root->data, which is wrong. Left subtree has smaller values.

3. Step 3: Correct the recursive calls

   Swap left and right calls: if (key < root->data) search left; else search right.

4. Final Answer:

   Swap left and right in recursive calls; should be key < root->data for left -> Option C

5. Quick Check:

   BST property fixes search direction [OK]

Hint: Left subtree < node, right subtree > node [OK]

Common Mistakes:

• Mixing left and right subtree directions
• Ignoring base case
• Changing return type unnecessarily

5. Given a BST with nodes inserted in this order: 25, 15, 50, 10, 22, 35, 70. You want to search for the value 22. How many nodes will the search function visit before finding 22?

hard

A. 2

B. 5

C. 4

D. 3

Solution

1. Step 1: Build BST structure from insertion order

   Insert 25 (root), then 15 (left of 25), 50 (right of 25), 10 (left of 15), 22 (right of 15), 35 (left of 50), 70 (right of 50).

2. Step 2: Trace search path for 22

   Start at 25 (visit 1), 22 < 25 go left to 15 (visit 2), 22 > 15 go right to 22 (visit 3), found key.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Nodes visited = 3 [OK]

Hint: Count nodes visited following BST search path [OK]

Common Mistakes:

• Counting nodes not visited
• Misplacing nodes in BST
• Stopping count before finding key