You’re given a binary tree, which is a structure where every node has at most two child nodes (left and right). Your task is to check if this tree is a Binary Search Tree.
To be a valid BST, the tree must follow these rules:
- Left Rule: All the nodes in the left subtree of a node must have values smaller than the value of that node.
- Right Rule: All the nodes in the right subtree of a node must have values greater than the value of that node.
- Recursive Rule: The above two rules must apply to every node in the tree, meaning the left and right subtrees of every node must also by valid BSTs.
Think of it as ensuring each node is correctly “sandwiched” between its parent node and the values in its subtrees while maintaining order across the entire tree. If all nodes follow this pattern, the tree is a valid BST.
Recursive Solution
In a BST, an in-order traversal (left → root → right) produces a sorted sequence of node values. To validate the BST, we simply ensure that this sequence is strictly increasing. This avoids additional bookkeeping, making it more efficient in both time and space.
• The tree’s structure inherently supports in-order traversal.
• Checking a sorted order aligns naturally with the BST property.
In-order traversal is a foundational pattern for processing sorted data in trees.
Steps
- Traverse each node and check if it satisfies the BST property:
- Left subtree nodes must be smaller than the current node.
- Right subtree nodes must be larger than the current node.
- Use recursion to validate all nodes, maintaining bounds for valid values.
- Return false as soon as violation is found.
class Solution {
public boolean isValidBST(TreeNode root) {
return inOrderTraversal(root, null);
}
private boolean inOrderTraversal(TreeNode node, Integer[] prev) {
if (node == null) return true;
// Check left subtree
if (!inOrderTraversal(node.left, prev)) return false;
// Validate current node
if (prev[0] != null && node.val <= prev[0]) return false;
// Update previous value
prev[0] = node.val;
// Check right subtree
return inOrderTraversal(node.right, prev);
}
}Line By Line Explanation
Step 1: Method Definition
public boolean isValidBST(TreeNode root) {
return inOrderTraversal(root, new Integer[1]);
}- This approach keeps the code modular and readable by separating the main logic (isValidBST) from recursive traversal (inOrderTraversal).
- Using new Integer[1] avoids global variables and allows previous values to be updated between recursive call efficiently.
Step 2: Base Case For Recursion
private boolean inOrderTraversal(TreeNode node, Integer[] prev) {
if (node == null) return true;- The use of a base case is a standard recursion practive to prevent infinite loops and ensure correctness.
Step 3: Traverse Left Subtree
if (!inOrderTraversal(node.left, prev)) return false;- Recursively checks the left subtree of the current node to ensure it satisfies the BST property.
- In a BST, all nodes in the left subtree must have values smaller than the current node. Traversing the left subtree first ensures that the tree is checked in in-order traversal.
Step 4: Validate The Current Node
if (prev[0] != null && node.val <= prev[0]) return false;- Comapares the current node’s value (node.val) with the previous node’s value stored in prev[0]. If the current value is lass than or equal to the previous value, the BST property is violated.
- The key BST property is that the in-order traversal must produce strictly increasing values. This comparison ensures that property is upheld.
Step 5: Update The Previous Value
prev[0] = node.val;- Updates prev[0] with the current node’s value. This ensures the next node in the traversal has an accurate “previous value” to compare against.
Step 6: Return The Result
return inOrderTraversal(node.right, prev);- Return the result.
Iterative Approach
Recursive and iterative approaches each have their strengths and weaknesses. Recursive solutions are often simpler, easier to read, and align naturally with problems like tree traversal, but they can run into stack overflow issues for deep inputs and may be harder to debug. Iterative solutions are more robust for large datasets, avoid stack limitations, and offer better control and performance, though they can be more verbose and less intuitive.
Key Trade-Offs:
• Recursive: Simpler and natural but risks stack overflow and can be slower.
• Iterative: Robust and efficient but more complex to write and understand.
Steps
1. Initialize an empty stack and a variable prev to store the last visited node value.
2. Traverse the tree iteratively using a stack for in-order traversal.
3. Check if the current node value is greater than prev.
4. If valid, update prev and continue; otherwise, return false.
5. Complete the traversal and return true if no violations are found
import java.util.Stack;
public class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
Integer prev = null;
while (!stack.isEmpty() || current != null) {
while (current != null) {
stack.push(current); // Push all left nodes onto the stack
current = current.left;
}
current = stack.pop(); // Visit the next node
// Check if the current value is greater than the previous value
if (prev != null && current.val <= prev) return false;
prev = current.val; // Update the previous value
current = current.right; // Move to the right subtree
}
return true; // No violations found
}
}- Initialize Stack, Current Node, and Previous
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
Integer prev = null;- A stack is created to manage the traversal
- The current point starts at the root of the tree
- prev tracks the value of the previously visited node during traversal.
2. Outer loop for Traversal
while (!stack.isEmpty() || current != null) {- The loop runs as long as there are nodes to process in the stack or the tree.
- Ensures all nodes are visited until both the stack and the current pointer are empty.
3. Traverse Left Subtree
while (current != null) {
stack.push(current); // Push all left nodes onto the stack
current = current.left;
}- Pushes all the left children of the current subtree onto the stack, moving as far left as possible.
- Mimics the recursive process of in-order traversal by focusing on the leftmost nodes first.
4. Visit Node
current = stack.pop(); // Visit the next node- Removes the top node from the stack
- Follows the in-order traversal order by visiting the node after processing its left subtree.
- Adheres to in-order traversal’s “left-root-right” sequence using a stack for explicit control.
5. Check BST Property
if (prev != null && current.val <= prev) return false;- Compares the current node’s value with prev to ensure the in-order sequence is strictly.
- If the current value is less than or equal to prev, the BST property is violated, and the function immediately returns false.
6. Update Previous Value
prev = current.val; // Update the previous value- Updates prev to the value of the current node, preparing for next comparison.
- Keeps track of the last node’s value to ensure subsequent nodes are larger maintaining the BST property.
7. Traverse Right Subtree
current = current.right; // Move to the right subtree- Moves the current pointer to the right child, continuing the in-order traversal.
- Completes in-order traversal by visiting nodes in “left-root-right” order
8. Return True
return true; // No violations found- Cleanly returns the result after completing the traversal.
Why This Code Works
1. Efficiency:
• Traverses the tree once, ensuring O(n) time complexity.
• Uses O(h) space for the stack, where h is the tree height.
2. Robustness:
• Avoids recursion to prevent stack overflow, making it suitable for very large or skewed trees.
3. Clarity:
• Maintains a straightforward structure with explicit stack management, making it easier to debug and understand.
4. Early Exit:
• Stops processing as soon as a BST violation is detected, saving unnecessary computations.
This iterative solution efficiently checks the BST property using an in-order traversal, ensuring correctness while minimizing space and time overhead.
