Binary Search Trees — Search, Insert, Delete, and Traversals Demystified | Chapter 12 of Intro to Algorithms

Binary search trees (BSTs) are a fundamental building block for dynamic sets, dictionaries, and efficient search algorithms in computer science. Chapter 12 of introduction to algorithms delivers a deep dive into the structure, operations, and efficiency of BSTs, revealing why they remain core to both academic theory and practical software design.

For a guided walkthrough, watch the podcast summary below—and subscribe to Last Minute Lecture for clear, chapter-by-chapter breakdowns of introduction to algorithms.

What Is a Binary Search Tree?

A binary search tree is a hierarchical data structure in which each node contains a key, optional satellite data, and pointers to its left child, right child, and parent. The defining binary-search-tree property states:

• All keys in a node’s left subtree are less than or equal to the node’s key.
• All keys in the right subtree are greater than or equal to the node’s key.

This property enables fast searching, inserting, and deleting by narrowing down possible locations based on key comparisons. Note that many different BSTs can represent the same set of values depending on insertion order.

Traversals: Inorder, Preorder, Postorder

The inorder tree walk visits the left subtree, the root, then the right subtree, outputting all keys in sorted order. Its running time is Θ(n) for a tree with n nodes. Other standard traversals include:

• Preorder: Root, left, right
• Postorder: Left, right, root

These traversals serve distinct purposes in tree processing, expression evaluation, and serialization.

Essential BST Operations

All core BST operations run in O(h) time, where h is the tree’s height:

• TREE-SEARCH: Finds a node with a given key, either recursively or iteratively.
• TREE-MINIMUM: Follows left children to find the smallest key.
• TREE-MAXIMUM: Follows right children to find the largest key.
• TREE-SUCCESSOR: Finds the next-higher node in the sorted order:
  • If the node has a right subtree, successor is the minimum in that subtree.
  • Otherwise, it’s the lowest ancestor for which the node is in the left subtree.
• TREE-PREDECESSOR: The mirror of successor, using the left subtree or right-ancestor logic.

Insertion: TREE-INSERT

Insertion starts at the root, tracing a path until it finds a NIL (empty) position where the new node should be placed. The operation updates parent and child pointers accordingly. The final shape of the tree—and thus future search times—depends on the order of insertions, which may or may not keep the tree balanced.

Deletion: TREE-DELETE and TRANSPLANT

Deleting a node from a BST must maintain the binary-search-tree property. There are three main scenarios:

1. No left child: Replace the node with its right child.
2. No right child: Replace with its left child.
3. Two children: Find the node’s successor, transplant it to the deleted node’s spot, and adjust subtrees accordingly.

The TRANSPLANT helper procedure is used to replace one subtree with another and update parent links, keeping the tree structure intact.

Efficiency and Tree Height

The running time of BST operations depends on the tree’s height h:

• Best case (balanced tree): h = Θ(log n), yielding fast O(log n) operations.
• Worst case (degenerate tree): h = Θ(n), where the tree becomes a linked list.
• Average case: Random insertions typically yield h = O(log n).

This is why balanced BSTs (e.g., AVL, Red-Black trees) are covered in later chapters to guarantee fast performance.

Key Concepts and Glossary

• Binary Search Tree: Ordered tree where left ≤ node ≤ right
• Inorder Tree Walk: Sorted traversal of the BST
• TREE-SEARCH / TREE-MINIMUM / TREE-MAXIMUM: Key BST queries
• TREE-SUCCESSOR / TREE-PREDECESSOR: Find next or previous node in order
• TREE-INSERT / TREE-DELETE: Core update operations
• TRANSPLANT: Helper for replacing subtrees
• Height: Path length from root to deepest leaf
• Balanced Tree: Maintains Θ(log n) height for efficiency
• Degenerate Tree: Linear (linked list) structure

Conclusion: BSTs as Algorithmic Foundations

Chapter 12 of introduction to algorithms establishes binary search trees as the cornerstone for efficient set and dictionary operations in computer science. Mastering BST operations prepares you for deeper study of self-balancing trees, advanced data structures, and fast algorithm design.

Watch the chapter summary video on YouTube and explore more algorithm walkthroughs with Last Minute Lecture.

Don’t miss future chapters—subscribe for clear, chapter-by-chapter explanations of introduction to algorithms and more!

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.