A Binary Search Tree stores values so that every node's left subtree contains only smaller values and every node's right subtree contains only larger values. This property allows insert and search in O(log n) average case by following a single path from root to leaf.
struct Node { int val; Node *left, *right; Node(int v):val(v),left(nullptr),right(nullptr){} };
Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val < root->val) root->left = insert(root->left, val);
else if (val > root->val) root->right = insert(root->right, val);
return root;
}
bool search(Node* root, int val) {
if (!root) return false;
if (val == root->val) return true;
return val < root->val ? search(root->left,val) : search(root->right,val);
}For every node N: all values in the left subtree are less than N.val, and all values in the right subtree are greater. This invariant must be maintained after every insert and delete.
Start at root. If target equals root.val, found. If target is less, recurse left. If greater, recurse right. Each comparison eliminates one subtree, giving O(log n) on balanced trees.
Search for where the value would be found. When you reach a null child, insert the new node there. The new node is always inserted as a leaf, maintaining the BST property trivially.
Inserting already-sorted data creates a degenerate tree (a linked list). Height becomes O(n) making all operations O(n). Self-balancing trees (AVL, Red-Black) solve this problem.
Quiz coming soon for this algorithm.