Code link: https://leetcode.com/problems/validate-binary-search-tree/

Constraint:

• The number of nodes in the tree is in the range [1, 104].
• -2^31 <= Node.val <= 2^31 - 1

Idea

For each node, we will need to check if its value is within certain range [min, max]. As we traverse downward, we have to update the range accordingly. Basically we need to update the upper bound when we go left and lower bound when we go right. Initially the range could be [-2^31 , 2^31 - 1]

• Attemp 1.

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isValidBSTHelper(TreeNode root, int min, int max) {
        if (root == null) {
            return true;
        }
        
        if (root.val <= min || root.val >= max) {
            return false;
        }
        
        return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max);
    }
}

This solution doesn't work for the case where a node contains the the value of (2^31 - 1) or (-2^31). For example given the case [2147483647], the output would be false where it should be true.

• Attemp 2 Recursive solution
  A nice for BST is that if we inspect its values with in-order way, it is an ascending sequence. With that in mind, we can first do an in-order traversal and keep track of all the values in this order. Then we just need to verify whether the numbers are monotonously increasing or not.

class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> inOrderPath = new ArrayList<>();
        isValidBSTHelper(root, inOrderPath);
        for (int i = 1; i < inOrderPath.size(); i++) {
            if (inOrderPath.get(i) <= inOrderPath.get(i - 1)) {
                return false;
            }
        }
        
        return true;
    }
    
    private void isValidBSTHelper(TreeNode root, List<Integer> inOrderPath) {
        if (root == null) {
            return;
        }
        
        isValidBSTHelper(root.left, inOrderPath);
        inOrderPath.add(root.val);
        isValidBSTHelper(root.right, inOrderPath);
    }
}

• Time: O(n) as in-order traversing and inspecting the list both take O(n).

• Space: O(n). Both recursion stack and the list take O(n).

• Attemp 3 Iterative solution:

class Solution {
   public boolean isValidBST(TreeNode root) {
       List<Integer> path = new ArrayList<>();
       TreeNode cur = root;
       Stack<TreeNode> st = new Stack<>();
       while (cur != null || !st.isEmpty()) {
           if (cur != null) {
               st.push(cur);
               cur = cur.left;
           } else {
               cur = st.pop();
               path.add(cur.val);
               cur = cur.right;
           }
       }
       
       for (int i = 1; i < path.size(); i++) {
           if (path.get(i) <= path.get(i - 1)) {
               return false;
           }
       }
       
       return true;
   }
}

• Time: O(n)
• Space: O(n) as both the stack and list has size up to n.
  Potenailly we could check for number sequence while traversing the tree, instead of checking it in later run:

				...
                if (path.size() > 0 && path.get(path.size() - 1) >= cur.val) {
                   return false;
               }
   			...