BST basics

In a binary search tree, every node's left subtree has smaller values; right subtree larger. Search/insert follow one path from root—O(h) time where h is height.

Search algorithm

1. Start at root
2. If target == value, found
3. If target < value, go left; else right
4. Null means missing

Search implementation

#include 

struct Node { int v; Node* L; Node* R; };

Node* search(Node* n, int t) {
    while (n) {
        if (t == n->v) return n;
        n = (t < n->v) ? n->L : n->R;
    }
    return nullptr;
}

int main() {
    Node r{8, nullptr, nullptr}, l{3, nullptr, nullptr}, rr{10, nullptr, nullptr};
    r.L = &l; r.R = &rr;
    std::cout << (search(&r, 3) ? "found\n" : "missing\n");
    return 0;
}

Degenerate BST

Inserting sorted 1,2,3,… into plain BST makes a linked list—height n. Use balanced tree or shuffle inserts in production.

Important interview questions and answers

1. Q: BST delete overview?
   A: Three cases: leaf, one child, two children (replace with inorder successor)—interview follow-up.
2. Q: map vs own BST?
   A: std::map is balanced BST—O(log n) guaranteed; hand-rolled BST must rebalance for guarantees.

Self-check

1. What is BST search complexity in terms of height h?
2. Why sorted inserts hurt plain BST?

Tip: BST search is O(h)—state height, not always log n without balance.