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.