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

💡 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