[Top Interview 150] 98. Validate Binary Search Tree

Solution)

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # Variable prev will save a value of a previous node
        # Variable check will save a bool of whether this BST is valid
        prev = -2**31 - 1
        check = True

        # Helper function that compares previous node value
        # with current ndoe value to validates BST
        def compare(root):
            # Marking prev and check as nonlocal to use them
            # in this inner helper function
            nonlocal prev, check

            # Base Case
            if not root: return

            compare(root.left)

            # If previous node's value is greater than or equal to
            # the current value, this BST is not valid
            if prev >= root.val:
                check = False
            prev = root.val

            compare(root.right)
            
        compare(root)
        # Return check 
        return check

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(1)
*n = number of nodes in a tree
 

Explanation)

To know if the tree is a vlalid BST, we only need to compare two nodes. The current node and the previous node.
 
When we iterate BST, we'll iterate it in inorder traversal. If we do that, we'll iterate nodes in an increasing order. Thus if BST is valid, the current node will always be greater than the previous node. 
 
Because of this, we'll validate BST by comparing the current node with the previous node.
 

1. Initialization)

Variable prev will save a previous node's value. Its initial value is -2**31 - 1 which is a minimum number that cannot be reached for nodes in this tree.
 
Variable check will save a boolean value of whether this tree is valid. Its initial value is True. 
 

def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 1. Initialization
        prev = -2**31 - 1
        check = True

 

2. Nonlocal & Base Case)

We'll make and utilize a helper function. This helper function will compare prev with the current nod's value.
 
Set prev and check as nonlocal so that the inner helper function can use those variables.
Then as a base case, if root is empty return None.
 

def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 1. Initialization
        prev = -2**31 - 1
        check = True

        def compare(root):
            # 2. Nonlocal & Base Case
            nonlocal prev, check
            if not root: return

 

3. Compare previous value with the current value)

To iterate nodes in an increasing order, we need to iterate in inorder traversal.
 
So we need to approach root.left first.
 
Then we'll compare prev with the current node's value.
If prev is greater than or equal to the current value, this tree is not a valid BST.
So convert check to False.
 
And make sure to update prev as the current value so that we can continue comparing. 
 

def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 1. Initialization

        def compare(root):
            # 2. Nonlocal & Base Case
            nonlocal prev, check
            if not root: return

            # 3. Compare previous value with current value
            compare(root.left)

            if prev >= root.val:
                check = False
            prev = root.val

            compare(root.right)

 

4. Run compare() function)

After defining the helper function compare(), run this function.
 
After the function is executed, our check will either hold True if BST is valid or hold False if BST isn't valid.
Thus return check at the end.
 

def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 1. Initialization

        def compare(root):
            # 2. Nonlocal & Base Case
            nonlocal prev, check
            if not root: return

            # 3. Compare previous value with current value
            compare(root.left)

            if prev >= root.val:
                check = False
            prev = root.val

            compare(root.right)
            
        # 4. Run compare() function
        compare(root)
        return check

 
 
 
I first had a O(n) space complexity solution. I had a list full of all the nodes' values to compare. However, I realized I only needed to compare a previous node with a current node. So instead of having a list, I used an int variable to save the previous node's value. 
 
Have a nice day :)