Validate Binary Search Tree
Problem Description
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys strictly less than the node's key.
- The right subtree of a node contains only nodes with keys strictly greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Output: true
Example 2:
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range [1, 104].
- -231 <= Node.val <= 231 - 1
Solve it on LeetCode
Approaches
1. Inorder Traversal Recursively
Intuition:
A Binary Search Tree (BST) has the property that for each node, all the nodes in its left subtree have smaller values and all the nodes in its right subtree have larger values. Performing an inorder traversal of a BST should produce a sorted array of values. If the inorder traversal yields a sorted sequence without any repeated values, then the tree is a valid BST.
Steps:
- Perform an inorder traversal to check if each node value matches a sorted sequence.
- Use a helper function to perform the inorder traversal recursively.
- Keep track of the last seen value during the traversal to ensure that each current node's value is greater.
Code:
- Time Complexity: O(N) where N is the number of nodes in the BST because each node is visited exactly once.
- Space Complexity: O(N) for the recursion stack.
2. Inorder Traversal Iteratively
Intuition:
We can simulate the recursive inorder traversal using a stack to achieve an iterative solution. We push nodes to the stack while moving left, and then pop them to process each as we move right. This allows us to validate the BST properties without a recursive helper function.
Steps:
- Use a stack to simulate the inorder traversal.
- Push nodes onto the stack while traversing left.
- As nodes are popped from the stack, check the sequence order similar to the recursive approach.
- Store the last visited node value to validate the sorted order.
Code:
- Time Complexity: O(N) due to visiting each node once.
- Space Complexity: O(N) due to stack usage.
3. Recursive Valid Range
Intuition:
Instead of relying on inorder traversal, directly utilize the properties of a BST. For each node, determine a valid range it should lie within. The left child must be less than the current node and the right child greater. By passing down this valid range, you can recursively validate the entire tree.
Steps:
- Use a helper function to pass down the minimum and maximum allowable values for each node.
- Check if the current node's value lies within the valid range.
- Recursively check the left subtree with an updated max value and the right subtree with an updated min value.
Code:
- Time Complexity: O(N), as each node is checked once.
- Space Complexity: O(N) in the worst case due to the recursion stack using space.