LeetCode #98: Validate Binary Search Tree

LeetCode Solutions

https://leetcode.com/problems/validate-binary-search-tree/description/

Given a binary tree, the goal is to 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 valid BSTs.

Algorithm:

  1. Define a recursive function isValidBSTHelper that takes the current node, minimum and maximum values as arguments.
  2. Check if the current node is None. If it is, return True since an empty tree is considered a valid BST.
  3. Check if the current node’s value is less than or equal to the minimum value or greater than or equal to the maximum value. If it is, return False as the node violates the BST property.
  4. Recursively call the isValidBSTHelper function on the left and right subtrees with updated maximum and minimum values. The left subtree should have a maximum value of the parent node’s value and the right subtree should have a minimum value of the parent node’s value.
  5. Return the logical and of the recursive calls on the left and right subtrees.

Here is the Python3 Solution:

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def isValidBSTHelper(node, minVal, maxVal):
            if node is None:
                return True
            if node.val <= minVal or node.val >= maxVal:
                return False
            return (isValidBSTHelper(node.left, minVal, node.val) and
                    isValidBSTHelper(node.right, node.val, maxVal))

        return isValidBSTHelper(root, float('-inf'), float('inf'))

We define the recursive isValidBSTHelper function to take in three arguments – the current node, the minimum and maximum values that the node’s value can take. If the current node is None, we return True since an empty tree is considered a valid BST. If the current node’s value is less than or equal to the minimum value or greater than or equal to the maximum value, we return False as the node violates the BST property. We then recursively call the isValidBSTHelper function on the left and right subtrees with updated maximum and minimum values. The left subtree should have a maximum value of the parent node’s value and the right subtree should have a minimum value of the parent node’s value. Finally, we return the logical and of the recursive calls on the left and right subtrees.

Time and Space Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree, since we visit each node only once. The space complexity of this solution is also O(n), since the maximum space used by the recursion stack is n. Therefore, this solution is both time and space-efficient.