# Solution by <monkeykingyan>

• #### 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 = 0; i < res.size() - 1; ++i) {
if (res.get(i) >= res.get(i + 1)) return false;
}
return true;
}
public void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
helper(root.left, res);
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 \$\$2O(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 pointer "preNode" and a flag,
where flag change its value only if this is not valid BST.

Java

``````class Solution {
TreeNode preNode;
int flag =1;
public boolean isValidBST(TreeNode root) {
preNode = null;
helper(root);
if (flag == 1)
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 = 0;
}
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 \$\$2O(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 the 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 similar 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)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.