Trees

BST Search

Search a binary search tree for one present and one absent value.

Algorithm

Basic Implementation

basic.cpp 
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
struct Node { int value; Node* left; Node* right; Node(int v, Node* l=nullptr, Node* r=nullptr): value(v), left(l), right(r) {} };
string render(Node* node) {
    if (node == nullptr) return "_";
    if (node->left == nullptr && node->right == nullptr) return to_string(node->value);
    return to_string(node->value) + "(" + render(node->left) + "," + render(node->right) + ")";
}
Node* sampleTree() {
    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}
string listString(const vector<int>& values) {
    stringstream out; out << "[";
    for (size_t i = 0; i < values.size(); i++) { if (i) out << ", "; out << values[i]; }
    out << "]"; return out.str();
}
bool search(Node* root, int target) { Node* node = root; while (node) { if (target == node->value) return true; node = target < node->value ? node->left : node->right; } return false; }
int main() { Node* root = sampleTree(); cout << (search(root, 5) ? "5 found" : "5 not found") << "\n"; cout << (search(root, 8) ? "8 found" : "8 not found") << "\n"; }

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot found

Complexity

  • Time: O(h) per search
  • Space: O(1) iterative

Implementation notes

  • In C++, each tree node is a struct Node with int value and raw Node* left / Node* right child links defaulting to nullptr.
  • sampleTree() allocates the canonical tree with nested new Node(...) calls. The source uses raw pointers, not smart pointers, and does not show a matching delete cleanup path.
  • search(Node* root, int target) is iterative: Node* node = root is the cursor, while (node) is the null check, and each branch reassigns the cursor to node->left or node->right.
  • Comparisons are scalar int tests. A match returns true; otherwise target < node->value chooses left and the else path chooses right.
  • The trace shows search 5 moving 4 -> right, 6 -> left, then matching 5; search 8 moves 4 -> right, 6 -> right, 7 -> right, then reaches null.
  • Output is streamed as conditional string literals: 5 found and 8 not found. Search itself mutates only the local cursor; the tree links are read-only after allocation.
search path A comparison chooses one subtree at each step, so whole branches are skipped.