98. Validate Binary Search Tree

# medium

We need a helper function to return each subtree's minimum and maximun values.

Solution 1:

1. helper function - max and min value in a subtree

2. isValid function - both of left and right subtrees are valid, left_max < root and right_min > root, then it's valid.

Python

// Some code
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        res = self.isBST(root)
        return res[2]
        
    def isBST(self, root):   # return a tuple: (minValue, maxValue, isValid)
        # ege case
        if root == None:
            return (float('inf'), float('-inf'), True)
        
        left = self.isBST(root.left)
        right = self.isBST(root.right)
        
        if root.val > left[1] and root.val < right[0] and left[2] and right[2]:
            isValid = True
        else:
            isValid = False
            
        minValue = min(min(left[0], right[0]), root.val)
        maxValue = max(max(left[1], right[1]), root.val)
        
        return (minValue, maxValue, isValid)

Java

final class TreeInfo {
    boolean isBST;
    long maxVal;
    long minVal;
    
    public TreeInfo(boolean isBST, long maxVal, long minVal) {
        this.isBST = isBST;
        this.maxVal = maxVal;
        this.minVal = minVal;
    }
}
class Solution {
    public boolean isValidBST(TreeNode root) {
        TreeInfo res = helper(root);
        return res.isBST;
    }
    
    public TreeInfo helper(TreeNode root) {
        if(root == null) return new TreeInfo(true, Long.MIN_VALUE, Long.MAX_VALUE);
        
        TreeInfo left = helper(root.left);
        TreeInfo right = helper(root.right);
        
        if(!left.isBST || !right.isBST) {
            return new TreeInfo(false, -1, -1);
        }
        
        if((root.val > left.maxVal) && (root.val < right.minVal))
            return new TreeInfo(true, Math.max(right.maxVal, root.val), Math.min(left.minVal, root.val));
        
        return new TreeInfo(false, -1, -1);
    }
}

Solution 2:

Compute inorder binary tree traversal, if whole list is ascending, then it's valid.

Java(iterative)

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        Integer prev = null;
        
        while(!stack.isEmpty() || root != null) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(prev != null && root.val <= prev)
                return false;
            
            prev = root.val;
            root = root.right;
        }
        return true;
    }
}

Solution 3：

逆向思维，如果parent tree是BST，那么left sub tree的下限是左子树的low，上限是parent node.val. 那么right sub tree的下限是parent node.val，上限是右子树的up. 默认上限是无穷大，下限是无穷小。每个node遍历一遍，时间复杂度和空间度为 $O(n)$

Python-iterative

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.isBSTChild(root)
    
    def isBSTChild(self, node, low = float('-inf'), upper = float('inf')):  #  -> list[max, min] 
        if node == None:
            return True
        
        if node.val <= low or node.val >= upper:
            return False
        
        if self.isBSTChild(node.left, low, node.val) == False or self.isBSTChild(node.right, node.val, upper) == False:
            return False
        
        return True

Python-recursive

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
            
        stack = [(root, float('-inf'), float('inf')), ] 
        while stack:
            root, lower, upper = stack.pop()
            if not root:
                continue
            val = root.val
            if val <= lower or val >= upper:
                return False
            stack.append((root.right, val, upper))
            stack.append((root.left, lower, val))
        return True