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

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