The Binary Search Tree

This chapter is about the binary search tree. A binary search tree is a binary tree in which every value in a node’s left subtree is smaller than the node’s value and every value in its right subtree is larger, so a search can rule out one subtree with each comparison.

After reading this chapter, you should be able to:

• Decide whether a binary tree is a binary search tree by checking each value against all of its ancestors
• Search, add, and remove values in a binary search tree by hand, including removing a node with two children through its in-order successor
• Implement search, add, and remove with a public method and a private recursive helper
• Trace search, add, and remove as a call stack that grows down the search path and unwinds back to the root
• Explain why an in-order traversal of a binary search tree visits its values in ascending order
• Implement an in-order iterator for a binary search tree with an explicit stack that pauses between calls to next
• Analyze the tree’s operations in terms of its height $h$: $O(h)$ for search, add, and remove, and amortized $O(1)$ per call to the iterator’s next
• Derive that a binary search tree with $n$ nodes has a height between about $\log n$ and $n-1$
• Explain that adding values in sorted order builds a degenerate tree

You can download the accompanying code for this chapter: starter and solution.

Sections

1. The Ordering Property
2. The Node and the Tree
3. Searching for a Value
4. Search in Code
5. Tracing a Search
6. Adding a Value
7. Add in Code
8. Tracing an Add
9. In-order Is Sorted
10. Minimum, Maximum, and Successor
11. Removing a Leaf or a Single Child
12. Removing a Node with Two Children
13. Remove in Code
14. Tracing a Remove
15. Iterating in Sorted Order
16. Tracing the Iterator
17. The Cost of the Iterator
18. How Short Can a Tree Be?