Welcome back! In our last lesson, we established the single most important rule of a binary search tree: the strict ordering invariant. We saw that this rule is global, meaning a node's key must be valid not just relative to its parent, but relative to all of its ancestors. This insight revealed why a simple local check is a common but incorrect approach to validating a BST.
Today, we will put that knowledge into action. Your goal is to be able to determine if any given binary tree is a valid BST. This is a classic coding interview problem, and mastering it requires translating the theoretical invariant into a robust algorithm. We will explore the two most common and efficient solutions, both of which correctly handle the global nature of the BST property.
The Problem with Local Checks
Before diving into the correct solutions, let's briefly revisit the trap we identified last time. It's tempting to traverse the tree and, for each node, simply check if node.left.key < node.key and node.key < node.right.key.
The video from NeetCode provides a crystal-clear example of why this fails.
Validate Binary Search Tree - Depth First Search - Leetcode 98
Watch this segment where the presenter sets up a tree that looks locally correct but violates the global BST invariant.
Pay close attention to the tree with root 5. The presenter walks through how each node satisfies the local check, but the tree as a whole is invalid. This happens from the initial example.
The node with key 4 is less than its parent 7, which is correct locally. However, 4 is in the right subtree of the root 5, so it must be greater than 5. Since it isn't, the tree is invalid. This confirms that any correct algorithm must somehow "remember" the constraints imposed by ancestors.
Solution 1: Recursive Validation with Bounds
The most direct way to enforce the global invariant is to pass the valid key range down through the tree during a traversal. For any given node, its key must fall within an (lower_bound, upper_bound) interval defined by its ancestors.
- When we traverse to a node's left child, the child's key must be less than the current node's key. The current node's key becomes the new
upper_boundfor the entire left subtree. - When we traverse to a node's right child, the child's key must be greater than the current node's key. The current node's key becomes the new
lower_boundfor the entire right subtree.
The same NeetCode video explains this recursive, depth-first search strategy beautifully.
Validate Binary Search Tree - Depth First Search - Leetcode 98
Now, watch the core of the video, which presents the correct recursive algorithm.
First, focus on the conceptual explanation from the whiteboard walkthrough, where the idea of passing negative infinity and positive infinity as initial bounds is introduced and the bounds are updated at each step. Then, see how this logic translates directly into a recursive Java implementation.
This approach is elegant because the state of the recursion (the low and high parameters) perfectly encodes the global constraints from all ancestors at any point in the tree. The Baeldung article you have also discusses this strategy, which you can use as a textual reference.
How to Validate a Binary Search Tree?
This article provides another look at the same algorithms. You can skim it to reinforce your understanding.
In section 3.2, find the explanation for the limits method. Then, in section 4.2, you can review the corresponding pseudocode, which shows the logic in a language-agnostic way.
Solution 2: Validation by In-order Traversal
There is another, equally powerful way to think about this problem. It relies on a different fundamental property of BSTs: an in-order traversal of a valid BST will always visit the keys in strictly ascending order.
Why? Because the definition of an in-order traversal is to visit:
- The entire left subtree (all smaller keys)
- The node itself
- The entire right subtree (all larger keys)
This recursive process naturally yields a sorted sequence if and only if the tree upholds the BST invariant at every node. Therefore, we can validate a tree by performing an in-order traversal and checking if the sequence of keys is sorted.
The following video from Nikhil Lohia explains this approach.
Validate Binary Search Tree (LeetCode 98) | Full solution with animations and visuals
This video presents the in-order traversal method as an alternative solution.
Watch the section from "focus on the inaudit reversal", where the core concept is introduced. Then, see how this is applied to both a valid and an invalid tree in the following segment, from verifying the idea.
This method can be implemented in two main ways:
- Perform a full in-order traversal, store all keys in a list, and then iterate through the list to check if it is sorted. This is straightforward but requires space proportional to the number of nodes, .
- A space-optimized approach: perform the in-order traversal, but instead of storing all keys, just keep track of the previously visited node's key. At each node, compare its key to the previous key. If you ever find a key that is less than or equal to the previous one, you can immediately stop and return
false. This uses only constant extra space (besides the recursion stack).
Algorithm Comparison
For a software engineering interview, you should be prepared to discuss the trade-offs of these two primary approaches.
| Approach | Time Complexity | Auxiliary Space Complexity | Notes |
|---|---|---|---|
| Recursive with Bounds | The space is for the recursion call stack, where is the height of the tree. This is the most common and often preferred solution. | ||
| In-order Traversal (List) | The space is dominated by the list used to store keys. Simple to code but less space-efficient. | ||
| In-order (Optimized) | Space is for the recursion stack. This is as efficient as the bounds method and demonstrates a deeper understanding. |
As you can see, both the "Recursive with Bounds" and the "Optimized In-order" methods are highly efficient, visiting each node once with space complexity determined by the tree's height.
Conclusion
In this lesson, you have moved from the theory of the BST invariant to the practical task of validating it. This is a foundational skill for working with BSTs and a frequent topic in technical interviews.
Here are the key takeaways:
- Global vs. Local: BST validation fails if you only check a node's immediate children. The algorithm must respect constraints from all ancestors.
- Bounds Propagation: A robust method is a recursive DFS that passes down a valid
(min, max)key range for each subtree. - In-order Property: A valid BST's in-order traversal always produces a sorted sequence of keys, providing an alternative validation strategy.
- Complexity: The most efficient solutions run in time and space. Being able to explain why is as important as implementing the code.
Now that we have solidified our understanding of the BST's structural rules, we are ready to analyze its performance. In our next lesson, we will derive the time and space costs for core BST operations as a function of the tree's height, which will directly explain why maintaining a balanced tree is so important.