Lesson notes
These notes explain the problem and current implementation. They are a reading companion, not a verbatim transcript of the recording.
A binary search tree organizes values so comparisons can select one subtree at each step. Under a strict ordering, every value in a node's left subtree is smaller and every value in its right subtree is larger. The recording explains that rule, navigation, and common operations. Duplicate keys need an additional policy if the API permits them.
Apply the rule to entire subtrees
Suppose the root is 10, its left child is 5, and 5 has a right child of 12. The local edge from 5 to 12 appears ordered, but 12 violates the root's left-subtree constraint. Checking only a node against its immediate children cannot validate the full tree. Ancestor bounds remain relevant farther down the path.
Searching uses those bounds in the other direction. A target below the current value can only be in the left subtree; a larger target can only be in the right. If the selected child does not exist, the search is complete without scanning the opposite subtree. That exclusion argument depends on the tree actually satisfying the ordering invariant.
Explain extrema and shape
The minimum is reached by following left links until none remains. That node can still have a right child, so it need not be a leaf. The maximum follows the corresponding right-link path and can have a left child. The recording's correction clarifies that distinction.
Operation costs depend on height. A balanced tree can provide logarithmic-height paths, while an unbalanced tree can become a chain. Inserting already sorted values into an ordinary unbalanced implementation illustrates this worst case. Naming the structure a binary search tree does not promise self-balancing behavior.
Keep result shape and duplicate policy explicit
A search might return a matching node, a boolean, or a stored value. The implementation lesson returns a node or an absent result. If equal values are allowed, decide whether insertion ignores them, stores counts, or consistently places them on a chosen side. Validation must use the same policy.
Continue with Implement a Binary Search Tree to trace insert and search. Then try BST Validate, whose inherited bounds catch the 12-under-5 counterexample. Use Tree Traversal to connect in-order visits with sorted output under the strict invariant.