Solution by <monkeykingyan>


  • 0

    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);
            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 $$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:

    1.jpg 2.jpg 3.jpg 4.jpg 5.jpg 6.jpg 7.jpg 8.jpg 9.jpg

    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)

Log in to reply
 

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