My log(log(n)) time and O(1) space solution.


  • 0
    M

    The idea is iterate in any order and compare every element on left is smaller than current element and every element on right is greater than current element.

    public class Solution {
        boolean isValid = true;
        public boolean isValidBST(TreeNode root) {
            
            if(root == null){
                return true;
            }
            traverse(root);
            
            return isValid;
        }
        public void traverse(TreeNode node){
            if(node == null){
                return;
            }
            // do something with node
           if(node.left != null){
               traverseAndCompareLeftSubTree( node.left, node);
           }
           if(node.right != null){
               traverseAndCompareRightSubTree( node.right, node);
           }
           
           //go left
           traverse(node.left);
           //go right
           traverse(node.right);
           
        }
        
        public void traverseAndCompareLeftSubTree(TreeNode node, TreeNode compareThis){
            if(node == null || compareThis == null){
                return;
            }
            if(node.val >= compareThis.val){
                isValid = false;
            }
            traverseAndCompareLeftSubTree(node.left, compareThis);
            traverseAndCompareLeftSubTree(node.right, compareThis);
            
        }
        public void traverseAndCompareRightSubTree(TreeNode node, TreeNode compareThis){
            if(node == null || compareThis == null){
                return;
            }
            if(node.val <= compareThis.val){
                isValid = false;
            }
            traverseAndCompareRightSubTree(node.left, compareThis);
            traverseAndCompareRightSubTree(node.right, compareThis);
            
        }
    
        
    }
    

Log in to reply
 

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