Hello! In our last lesson, we took a journey through the history of binary search trees, discovering why they were invented and how early challenges, like deletion, revealed the critical importance of maintaining tree balance. We ended by noting that the promise of performance is built on a single, powerful rule.
Today, we will focus entirely on that rule: the strict binary search tree ordering invariant. This is the fundamental contract of the data structure. Understanding it with precision is the key to correctly implementing every BST operation and is a common focus in technical interviews. By the end of this lesson, you will be able to state this invariant and explain the subtle but crucial implications of its recursive nature.
The Core Rule: Symmetric Order
At its heart, a Binary Search Tree (BST) is a binary tree that organizes its keys in a specific, "symmetric" order. This ordering is what allows us to discard half of the remaining keys at each step of a search, mirroring the efficiency of binary search in a sorted array.
The following resource from Sedgewick and Wayne's "Algorithms" provides a concise, formal definition of this property.
These lecture slides clearly define what makes a binary tree a binary search tree.
On page 3 of the PDF, find the slide titled "Binary search trees". Focus on the definitions of "Binary tree" and, more importantly, "Symmetric order". This section states the core invariant that we will be exploring.
As the reading states, the invariant for a BST is defined as follows: for any given node in the tree, its key must be larger than all keys in its left subtree and smaller than all keys in its right subtree.
Let's rephrase this for maximum clarity, using the convention left < root < right. For any node N with key k:
- Every key in the entire left subtree of
Nmust be strictly less thank. - Every key in the entire right subtree of
Nmust be strictly greater thank.
The word "strictly" is important. In this course, and in many common definitions used in interviews, we will adhere to a no-duplicate key policy. If a key is already in the tree, we don't insert it again.
The Invariant is Recursive and Global
The most critical part of this definition is that it applies recursively to every node in the tree. It's not enough for the rule to hold true just for the root node. Every single node must satisfy the BST invariant with respect to its own subtrees.
This recursive nature leads to a common and subtle trap. It's easy to mistakenly think you can validate a BST by just checking if node.left.key < node.key < node.right.key for every node. This check is local and is insufficient. The invariant is global: a node's key must respect the constraints imposed by all of its ancestors, not just its direct parent.
The next video, framed around the common interview problem "Validate Binary Search Tree," offers an excellent visual explanation of this distinction.
Validate Binary Search Tree (LeetCode 98) | Full solution with animations and visuals
This video does a superb job of not only defining the BST invariant but also demonstrating why a simple, local check fails.
Please watch the following segments: The introduction: This clearly states the recursive property of the invariant. The examples: Observe how the rule is applied to determine if two sample trees are valid BSTs. The trap: This is the most important part of the video. It presents a counterexample of a tree where every node satisfies the local property, but the global BST invariant is violated. This is a key insight. Duplicate nodes: This short clip confirms the strict, no-duplicate policy we are using.
As the video masterfully demonstrated, the check must be global. The node with key 10 was locally valid because 10 < 15. However, it violated the global invariant because it was in the right subtree of the root 11, and therefore its key was required to be greater than 11.
This global property can be formalized by thinking about bounds. For any node N, its key must lie within a valid range (lower_bound, upper_bound).
- The
lower_boundis the key of the nearest ancestor for whichNis in the right subtree. - The
upper_boundis the key of the nearest ancestor for whichNis in the left subtree.
In the video's counterexample, for the node with key 10:
- Its parent is
15. Since10is in the left subtree of15, the parent imposes an upper bound of15. The range is(-∞, 15). - Its ancestor is
11. Since10is in the right subtree of11, the ancestor imposes a lower bound of11. The range is(11, +∞). - To be valid, the key
10must satisfy both constraints. It must be in the range(11, 15). Since it is not, the tree is invalid.
Conclusion
In this lesson, we have focused on the single most important rule in the world of binary search trees. Let's summarize the key takeaways:
- The Strict Ordering Invariant: For any node
Nwith keykin a BST, all keys in the left subtree must be less thank, and all keys in the right subtree must be greater thank. We assume a no-duplicate key policy. - Recursive and Global: This invariant must hold true for every node in the tree.
- The Ancestor Constraint: A node's validity depends not just on its parent, but on constraints imposed by all of its ancestors. A simple local check is not sufficient to validate a BST.
You now have a deep understanding of the rule that makes a BST work. In our next lesson, we will put this knowledge into practice. We'll tackle the problem shown in the video: "Determine whether a labeled binary tree satisfies the BST ordering invariant." We will develop a robust algorithm that correctly handles the global nature of the invariant by propagating the valid key range down the tree.