0098. Validate BST

Medium | Binary Search Tree + Recursion / Stack | 28 ms (94.97%), 17.7 MB (95.43%)

❓ Problem Statement

Source: LeetCode - Validate Binary Search Tree GitHub: Solution / Performance

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.

• The right subtree of a node contains only nodes with keys greater than the node's key.

• Both the left and right subtrees must also be binary search trees.

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].

• -2^31 <= Node.val <= 2^31 - 1

💡 Ideas

Keep maintaining the "Upper Bound" and "Lower Bound" while visiting.

• For visiting the left-child node, we update the upper bound by the current node's value and keep the lower bound (All child nodes in the left-subtree should not have values greater than their parent.)

• For visiting the right-child node, we update the lower bound by the current node's value and keep the upper bound (All child nodes in the right-subtree should not have values less than their parent.)

🤖 Python3

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # (base case)
        if not root.left and not root.right: return True
        
        # ==================================================
        #  Tree + DFS + Stack                (Iterative)   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        stack = [(root, float('-inf'), float('inf'))]
        while stack:
            node, lower, upper = stack.pop()
            
            if node.val >= upper or node.val <= lower: return False
            
            # (left  sub-tree) set UPPER bound to current node's value (<= curValue)
            if node.left : stack.append( (node.left,  lower,    node.val) )
            
            # (right sub-tree) set LOWER bound to current node's value (>= curValue)
            if node.right: stack.append( (node.right, node.val, upper) )
                
        return True
    
    '''
    # ==================================================
    #  Tree + DFS + Stack                (Recursive)   =
    # ==================================================
    # time  : O(n)
    # space : O(n)

    def _isValidBSTHelper(self, node, lower, upper):
        if not node: return True

        if ((upper > node.val > lower)                              and
            self._isValidBSTHelper(node.left,  lower,    node.val ) and
            self._isValidBSTHelper(node.right, node.val, upper)):
            return True

        return False

    def isValidBST(self, root: TreeNode) -> bool:
        # (base case)
        if not root.left and not root.right: return True

        return self._isValidBSTHelper(root, float('-inf'), float('inf'))
    '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
     
    public boolean isValid(TreeNode node, long lower, long upper) {
        if(node == null) return true;
        
        return (lower < node.val && node.val < upper) &&
               isValid(node.left, lower, node.val)    && 
               isValid(node.right, node.val, upper);
    }
    
    public boolean isValidBST(TreeNode root) {
        if(root.left == null && root.right == null) return true;
        
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
}