{x}
blog image

Validate Binary Search Tree

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.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

Solution Explanation: Validating a Binary Search Tree

This problem asks us to determine if a given binary tree is a valid Binary Search Tree (BST). A BST follows these rules:

  1. The left subtree of a node contains only nodes with keys less than the node's key.
  2. The right subtree of a node contains only nodes with keys greater than the node's key.
  3. Both the left and right subtrees must also be binary search trees.

Approach: In-order Traversal and Recursion

The most efficient way to solve this problem leverages the property of in-order traversal in a BST. An in-order traversal of a BST will visit nodes in ascending order. If we perform an in-order traversal and the values we encounter are not strictly increasing, the tree is not a valid BST.

The solution uses a recursive depth-first search (DFS) approach combined with in-order traversal. A helper function dfs recursively explores the tree:

  1. Base Case: If the current node is null (empty), it's a valid subtree, so return true.

  2. Recursive Calls: First, recursively check the left subtree (dfs(root.left)). If the left subtree is invalid, the entire tree is invalid, so return false.

  3. Value Comparison: After the left subtree is validated, check if the current node's value is greater than the previous node's value (prev). prev is a variable (global in some implementations, passed as a parameter in others) that tracks the value of the previously visited node. If the current node's value is not greater than prev, it violates the BST property, so return false.

  4. Update prev: Update prev to the current node's value.

  5. Right Subtree Check: Recursively check the right subtree (dfs(root.right)). If invalid, return false.

  6. Valid Subtree: If all checks pass, the current subtree is valid, so return true.

The initial call to dfs starts with prev set to negative infinity (-inf) to ensure that the first node's value is always greater.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the tree. This is because we visit each node exactly once during the in-order traversal.

  • 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 equal to 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.

Code Implementation (Python3)

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(root: Optional[TreeNode], prev: int) -> bool:
            if not root:
                return True
            if not dfs(root.left, prev):
                return False
            if root.val <= prev:
                return False
            return dfs(root.right, root.val)
 
        return dfs(root, -float('inf'))

The other languages (Java, C++, Go, TypeScript, Rust, Javascript, C#) follow the same logical structure, with minor syntactic differences specific to each language. The core algorithm remains consistent across all implementations.