Chapter 12: Binary Search Trees: Querying, Insertion, and Deletion

An inorder traversal — visiting the left subtree, then the root, then the right subtree — visits all nodes in sorted order in Θ(n) time, with preorder and postorder traversals available for other purposes. All core query operations run in O(h) time proportional to the tree's height h: TREE-SEARCH finds a node with a given key recursively or iteratively, TREE-MINIMUM and TREE-MAXIMUM follow left or right pointers to their terminus, and TREE-SUCCESSOR and TREE-PREDECESSOR locate the next or previous key in sorted order by either descending into the appropriate subtree or climbing to the relevant ancestor. Insertion places a new node by traversing from the root to the correct NIL position while tracking the parent, taking O(h) time, though the resulting tree shape — and therefore height — depends entirely on insertion order. Deletion handles three cases: a node with no left child is replaced by its right child, a node with no right child by its left, and a node with two children is replaced by its inorder successor using the TRANSPLANT helper subroutine that rewires parent links cleanly. The chapter closes by confronting the critical dependency on height: a balanced tree yields h = Θ(log n) and efficient O(log n) operations, while a degenerate tree built from sorted insertions degrades to h = Θ(n), motivating the balanced BST variants introduced in subsequent chapters.