Overview

This chapter introduces binary search trees (BSTs), a fundamental data structure that supports all major dynamic-set operations—SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and DELETE—in time proportional to the tree's height. BSTs serve as both dictionaries and priority queues. The chapter covers the BST property, tree traversals, querying, insertion, deletion, and proves that a randomly built BST has expected height O(lg n).

Key Concepts

• Binary search tree property: For any node x, all keys in x's left subtree are ≤ x.key, and all keys in x's right subtree are ≥ x.key. This ordering invariant enables efficient searching by eliminating half the remaining candidates at each step.

• Node structure: Each node stores key, left, right, and p (parent) pointers, plus optional satellite data. T.root points to the root; NIL represents absent children or parent.

• Height: The critical parameter. Operations run in O(h) where h is the tree height. For n nodes, h ranges from ⌊lg n⌋ (balanced) to n − 1 (degenerate chain).

• Tree walks: Recursive traversals that visit every node.

• Inorder walk: Visit left subtree, then root, then right subtree. Produces keys in sorted order.

• Preorder walk: Visit root before subtrees.

• Postorder walk: Visit root after subtrees.

• Randomly built BST: A BST formed by inserting n keys in a uniformly random order (each of the n! permutations equally likely). Its expected height is O(lg n) (Theorem 12.4).

Algorithms and Techniques

Inorder Tree Walk

INORDER-TREE-WALK(x): If x ≠ NIL, recursively walk x.left, print x.key, then recursively walk x.right. Produces sorted output.

• Theorem 12.1: Takes Θ(n) time on an n-node subtree (each node visited exactly once; proof by substitution with T(n) ≤ (c+d)n + c).

Searching

• TREE-SEARCH(x, k): Recursive—compare k with x.key; go left if k < x.key, right if k > x.key, return x if equal or NIL if absent.
• ITERATIVE-TREE-SEARCH(x, k): Same logic in a while loop, typically more efficient on real hardware.
• Both run in O(h) time, following a single root-to-leaf path.

Minimum and Maximum