Qustion Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example :
/ \
Binary tree [,,], return true.
Example :
/ \
Binary tree [,,], return false.
Write Before
The problem is same to the BST Inorder Traversal: LeetCode 94 !!! Why?
Because the inorder traversal get the order from root.left -> root -> root.right,
if the ValidBST is true, the inorder traversal is ascending order.
How to implement inorder traversal in BST?
->Recursive Method
->Iterative Method
->Morris Method
The tutorial following have all the detail of inorder traversal.
BST inorder Traversal
Approach #1.1 Recursive [Accepted]
Detail Explanation
The first method to solve this problem is using recursive.
This is the classical method and straightforward. we can define a helper function to implement recursion.
We use the property of the BST, where root.left.value< root.value< root.right.value
The java code is as following:
Java
public class Solution{
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
return helper(root, Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean helper(TreeNode root, long minValue, long maxValue)
{
if(root == null) return true;
if(root.val<=minValue||root.val>=maxValue) return false;
return helper(root.left, minValue, root.val) && helper(root.right, root.val, maxValue);
}
}
Complexity Analysis
- Time complexity : O(n) . The time complexity is O(n) because the recursive function is T(n)=2∗T(n/2)+1 .
- Space complexity : O(n) .
Approach #1.2 Inorder Traversal(Recursive + ArrayList) [Accepted]
Detail Explanation
Using recursive method to traverse BST and put the value into an array,
then check if the array is ordered or not.
Java
public class Solution2 {
public boolean isValidBST(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
helper(root, res);
for (int i = ; i < res.size() - ; ++i) {
if (res.get(i) >= res.get(i + )) return false;
}
return true;
}
public void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
helper(root.left, res);
res.add(root.val);
helper(root.right, res);
}
}
Complexity Analysis
-
Time complexity : O(n) . The recursive complexity is O(n) and we have to traverse the array then where time complexity is O(n) .
So the overall time complexity is 2∗O(n) equal to O(n) .
- Space complexity : The worst case for recursive is O(n) , and we need O(n) extra space for array, So the overall time complexity is 2O(n) equal to O(n) .
Approach #1.3 Inorder Traversal(Recursive Without ArrayList) [Accepted]
Detail Explanation
We can compare the value in the helper function.
This is almost same method strategy above,
the only change is instead of adding the value into the result list,
we have to check if the current value is larger than the previous one.
So, we need a poniter “preNode” and a flag,
where flag change its value only if this is not valid BST.
Java
class Solution {
TreeNode preNode;
int flag =;
public boolean isValidBST(TreeNode root) {
preNode = null;
helper(root);
if (flag == )
return true;
else
return false;
}
public void helper(TreeNode root) {
if (root == null) return;
helper(root.left);
if(preNode== null){
preNode = root;
}else
{
if(root.val<=preNode.val)
{
flag = ;
}
preNode = root;
}
helper(root.right);
}
}
Complexity Analysis
-
Time complexity : O(n) . The recursive complexity is O(n) but the worst case to find the tree is not the Valid BST still need O(n) .
So the overall time complexity is 2∗O(n) equal to O(n) .
- Space complexity : O(n) .
Approach #2 Inorder Traversal(Iterative Method) [Accepted]
Detail Explanation
We need a stack to implement this method. Similiar to the inorder traversal, the only different is we have curr pointer and pre pointer,
every time we pop from stack, we have to check the value of curr and pre.
Java
public class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root, pre = null;
while (curr != null || !stack.empty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
TreeNode temp = stack.pop();
if (pre != null && temp.val <= pre.val) return false;
pre = temp;
curr = temp.right;
}
return true;
}
}
```
**Complexity Analysis**
* Time complexity : $$O(n)$$.
* Space complexity : $$O(n)$$.
---
Approach #3 Inorder Traversal(Morris Method) [Accepted]
Detail Explanation
The strategy is similiar with the Morris Method in Inorder BST Traversal problem, but we need 3 extra pointers.
The java code is as follows:
Java
class Solution {
public boolean isValidBST(TreeNode root) {
TreeNode pre = null, curr = root, temp = null;
while(curr != null) {
if(curr.left == null) {
if(pre != null && pre.val >= curr.val)
return false;
pre = curr;
curr = curr.right;
}
else {
temp = curr.left;
while(temp.right != null && temp.right != curr)
temp = temp.right;
if(temp.right == null) { // left child has not been visited
temp.right = curr;
curr = curr.left;
}
else { // left child has been visited already
temp.right = null;
if(pre != null && pre.val >= curr.val)
return false;
pre = curr;
curr = curr.right;
}
}
}
return true;
}
}
How it works?
Let us go through the coding step by step:
Complexity Analysis
- Time complexity : O(n) .
- Space complexity : O(1) . The space complexity of Morris Traversal is O(1) because it just needs 3 “assisting” pointers. (TreeNode curr, TreeNode temp and TreeNode pre)
1