## What is it? A Binary Search Tree (BST) is a binary tree where every node satisfies the BST property: all values in the left subtree < node value < all values in the right subtree. This property enables efficient search, insertion, and deletion. ## How it works **Search:** - Compare target with current node; go left if smaller, right if larger; return node if equal **Insert:** - Search for the position where the new node would be, insert there as a leaf **Delete:** - Leaf → remove directly - One child → replace node with its child - Two children → replace with in-order successor (smallest in right subtree), delete that successor **In-order traversal** produces elements in sorted order. ## When to use - Dynamic sorted sets (frequent insert/delete + search) - Range queries (all elements between A and B) - Predecessor/successor queries ## Key Points - Average case: O(log n) for all operations - Worst case: O(n) when tree becomes a chain (degenerate BST from sorted input) - Balanced BSTs (AVL, Red-Black) guarantee O(log n) worst case - In-order traversal → sorted sequence