Imagine arranging a deck of numbered cards so that each choice sends you toward smaller or larger cards. A binary search tree (BST) organizes values this way. Each node has up to two children: every value in its left subtree is less than or equal to its value, and every value in its right subtree is greater. Equal values go left by convention. section 11.16 section 11.7
The ordering rule guides the main operations:
- Search compares a value with the current node, then follows the appropriate branch. section 11.20 section 11.7
- Insert follows the same path as a search until it finds an empty child position. If the tree is empty, the new node becomes its root. section 11.10
- Find the minimum by following left children; find the maximum by following right children. section 11.9
- Delete locates the value, then reconnects nodes according to whether the target has zero, one, or two children. section 11.12
What insertion order changes
Insert values from smallest to largest and each new node extends the right-hand branch. The result resembles a linked list, not a short branching tree. Inserting from largest to smallest creates the opposite problem. section 11.17
Search, insertion, deletion, minimum, maximum, predecessor, and successor each take O(h) time, where h is tree height. In a skewed tree, height can reach n; a balanced BST keeps it at O(log(n)). Shuffling input may reduce the chance of skew but cannot guarantee balance. Balanced variants provide stronger guarantees. section 11.20 section 11.17 section 11.19
An in-order traversal—left subtree, node, right subtree—visits BST values in sorted order. BSTs can make insertion and deletion faster than in sorted arrays, but their links use more memory and their code is more complex. section 11.13 section 11.6
def find_max_in_subtree(self):
parent = None
node = self
while node.right() is not None:
parent = node
node = node.right()
return node, parent
This Python method follows right-child links to find the maximum of a subtree and returns both that node and its parent. section 11.9
