Validate Binary Search Tree medium

Problem Statement

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.

Example 1

Input: root = [2,1,3] Output: true

Example 2

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

Steps

  1. Recursive Approach: We'll use a recursive helper function to traverse the tree.
  2. In-order Traversal (Implicit): The core idea is that an in-order traversal of a BST will yield a sorted list. We'll implicitly perform an in-order traversal by recursively checking the left subtree, then the node itself, and finally the right subtree. We track the minimum and maximum allowable values for each subtree.
  3. Validation: For each node:
    • Its value must be greater than the maximum value seen in its left subtree (or -inf initially).
    • Its value must be less than the minimum value seen in its right subtree (or inf initially).
    • Recursively check the left and right subtrees with updated minimum and maximum bounds.

Explanation

The recursive function isValidBST takes the current node, a minimum bound (min), and a maximum bound (max). It returns True if the subtree rooted at the current node is a valid BST within those bounds, and False otherwise.

The base cases are:

  • If the node is None, it's a valid BST (empty subtree).
  • If the node's value is outside the given bounds (node.val <= min or node.val >= max), it's not a valid BST.

The recursive step checks the left and right subtrees:

  • The left subtree must be a valid BST with a maximum bound of node.val - 1.
  • The right subtree must be a valid BST with a minimum bound of node.val + 1.

Code

import math

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:
        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, -math.inf, math.inf)

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N, resulting in O(N) space complexity. In the best case (a balanced tree), H is logâ‚‚(N), resulting in O(log N) space complexity.