The BST Rule, Searching and Inserting

A tree with a rule

In a binary search tree (BST), for every node: everything in its left subtree is smaller and everything in its right subtree is bigger.

Think of it like this: It's binary search built into the shape of the data: at each node ask “smaller or bigger?” and ignore the other side.

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node *left, *right;
    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int value) {
    if (!root) return new Node(value);           // found the empty spot
    if (value < root->value) root->left = insert(root->left, value);
    else if (value > root->value) root->right = insert(root->right, value);
    return root;                                  // duplicates are ignored
}

bool contains(Node* root, int target, int& steps) {
    steps = 0;
    while (root) {
        steps++;
        if (target == root->value) return true;
        root = target < root->value ? root->left : root->right;
    }
    return false;
}

void inorder(Node* n) {
    if (!n) return;
    inorder(n->left);
    cout << n->value << ' ';
    inorder(n->right);
}

int main() {
    Node* root = nullptr;
    for (int v : {50, 30, 70, 20, 40, 60, 80, 30}) root = insert(root, v);
    inorder(root);
    cout << endl;
    int steps;
    bool found = contains(root, 60, steps);
    cout << "60: " << found << " in " << steps << " steps" << endl;
    found = contains(root, 65, steps);
    cout << "65: " << found << " in " << steps << " steps" << endl;
    return 0;
}

Output

20 30 40 50 60 70 80 
60: 1 in 3 steps
65: 0 in 3 steps

Notice: inorder traversal of a BST prints the values in sorted order. Search and insert take O(height) steps – about log₂ n for a balanced tree.