Iterative Inorder BST Validation

In our last lesson, we focused on the theoretical trade-offs between recursive and iterative DFS, particularly concerning space usage and the risk of stack overflow. We concluded that while recursion is often more concise, the iterative approach provides robustness against deep or skewed data structures.

Today, we will put that knowledge into practice by applying our iterative traversal skills to a classic and fundamental problem: validating a Binary Search Tree (BST). This lesson will show you how a specific traversal order—inorder—has a special property that can be elegantly exploited to solve this problem. Your goal is to master the logic for validating a BST using an iterative inorder traversal, a common pattern in coding interviews.

The True Definition of a Binary Search Tree

Before diving into the algorithm, it's critical to have a precise understanding of what makes a Binary Search Tree valid. A simple definition can be misleading. A BST is a binary tree where for every node, the following properties must hold true:

1. Left Subtree Property: All values in the node's left subtree must be strictly less than the node's own value.
2. Right Subtree Property: All values in the node's right subtree must be strictly greater than the node's own value.
3. Recursive Structure: Both the left and right subtrees must also be valid Binary Search Trees.
4. No Duplicates: By this strict definition, duplicate values are not allowed.

The most common mistake is to only check a node's immediate children. However, the properties must hold for the entire subtree, which includes all descendants, not just the direct children.

The image below illustrates this common pitfall. In the "Invalid" tree on the left, node 4 is correctly less than its parent 5. However, 4 is in the right subtree of the root node 5 (via node 4's parent, which is also 4, oh that seems to be a mistake in the image text, let's look at the structure). The node with value 4 is a left child of node 5, but in the invalid tree, it is a right child of node 1. Wait, no. The invalid tree on the left is root=5, left=1, right=4. In 1's subtree, we have 3 and 6. This tree is invalid because 4 is less than 5, but it's in the right subtree. The node 4 is also the parent of 3 and 6, which violates the BST property locally. Let's focus on the ancestor rule. The node with value 4 is in the right subtree of node 1 which is fine, but it is also in the left subtree of node 5. This violates property 1, as 4 is not less than 1. The structure is confusing. Let's look at another example.

This "ancestor" rule is what trips many people up. A node must respect the constraints imposed by all of its ancestors. The video below explains this common mistake with another excellent example.

The Power of Inorder Traversal

So, how can we efficiently validate the entire structure? The key lies in a property of one of the traversal methods we've studied: an inorder traversal of a valid BST will always visit the nodes in ascending, sorted order.

Let's think about why. The inorder traversal pattern is Left -> Root -> Right. For any given node in a BST:

• All nodes in the Left subtree are smaller.
• The Root node is in the middle.
• All nodes in the Right subtree are larger.

When applied recursively, this naturally produces a sorted sequence.

The following video provides a great visualization of this concept.

This gives us a powerful new strategy. We can traverse the tree and check if the sequence of node values is sorted. If it is, the tree is a valid BST. If we find any two adjacent elements in the traversal that are out of order, we can immediately conclude it's not a BST.

The Iterative Inorder Validation Algorithm

While we could perform an inorder traversal, store all the values in an array, and then check if the array is sorted, this would require $O(N)$ auxiliary space for the array. We can do better.

By leveraging our iterative inorder traversal, we can perform this check on the fly with only $O(H)$ space for the stack (where $H$ is the tree's height). This is the "in-place" approach.

The algorithm is a small but crucial modification of the standard iterative inorder traversal:

1. Initialize an explicit stack and a prev_node pointer, setting it to null.
2. Start with the current_node at the root.
3. Use the familiar while loop that continues as long as current_node is not null or the stack is not empty.
4. Inside the loop, push all left children onto the stack until you hit null.
5. Pop a node from the stack. This is the next node in the "inorder" sequence. This is our visit step.
6. Validation Check: Before proceeding, compare the popped node's value with prev_node's value. If prev_node is not null and its value is greater than or equal to the current node's value, the sorted property is violated. The tree is not a BST, and we can immediately return false.
7. If the check passes, update prev_node to be the current node.
8. Finally, move to the right child (current_node = current_node.right) to continue the traversal.
9. If the entire traversal completes without returning false, the tree is a valid BST, and we can return true.

This approach is highly efficient because it stops at the very first violation it finds.

Implementation and Walkthrough

The logic described above is implemented clearly in the following resource. We will use this as our reference implementation.

Let's trace this algorithm on an invalid tree to see it in action. Consider the "Invalid" tree from the image we saw earlier, which has this structure (simplified for clarity): root=5, left=1, right=7, 7.left=4.

Consider the rightmost tree: root=8, left=6, 6.left=1, 6.right=9.

1. Init: stack = [], prev = null, root = Node(8).
2. Go Left:
   • Push 8. stack = [8]. root = Node(6).
   • Push 6. stack = [8, 6]. root = Node(1).
   • Push 1. stack = [8, 6, 1]. root = null.
3. Pop & Visit:
   • Pop 1. root = Node(1).
   • Check: prev is null. The check passes.
   • Update: prev = Node(1).
   • Go Right: root = root.right which is null.
4. Pop & Visit:
   • root is null, so we pop 6. root = Node(6).
   • Check: prev.data (1) < root.data (6). The check passes.
   • Update: prev = Node(6).
   • Go Right: root = root.right which is Node(9).
5. Go Left:
   • Push 9. stack = [8, 9]. root = root.left which is null.
6. Pop & Visit:
   • root is null, so we pop 9. root = Node(9).
   • Check: prev.data (6) < root.data (9). The check passes. Wait, this is an interesting case. The local check between 6 and 9 is fine.
   • Update: prev = Node(9).
   • Go Right: root = root.right which is null.
7. Pop & Visit:
   • root is null, so we pop 8. root = Node(8).
   • Check: prev.data (9) is NOT less than root.data (8). The condition root.data <= prev.data (i.e., 8 <= 9) is TRUE.
   • VIOLATION! The inorder sequence would have been 1, 6, 9, 8, ..., which is not sorted. We return false.

The algorithm correctly identified the invalid structure without needing to know about ancestor-descendant relationships explicitly; the violation naturally emerged from the inorder sequence.

Complexity and Alternative Solutions

• Time Complexity: $O(N)$, as we visit each node at most once.
• Space Complexity: $O(H)$, where $H$ is the height of the tree. This is the space used by the explicit stack. In the worst case of a skewed tree, this becomes $O(N)$, a point we discussed in the last lesson.

It is worth noting another very common and equally efficient solution that uses recursion with min/max boundaries. In that approach, you pass down a valid range (min_val, max_val) for each node and check if the node's value falls within it. While we focused on the inorder method today, being aware of the boundary-check method is valuable for your algorithmic toolkit. You can review this alternative in the EnjoyAlgorithms article.

Conclusion

Today, you've learned a practical and efficient pattern for validating a Binary Search Tree. This lesson connected our previous work on iterative traversals to a real-world problem, reinforcing your understanding of both topics.

Key Takeaways:

• A valid BST must satisfy its properties with respect to all ancestors, not just its immediate parent.
• The inorder traversal of a valid BST always produces a sequence of nodes sorted in ascending order.
• We can exploit this property to validate a BST by performing an iterative inorder traversal and checking for any violation of the sorted order on the fly.
• This approach is efficient, with a time complexity of $O(N)$ and space complexity of $O(H)$.

In our next lesson, we will continue to build on our DFS patterns by tackling another classic problem: finding all root-to-leaf paths that sum to a target value. This will further solidify your ability to adapt traversal templates to meet specific problem requirements.