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. This function will take three arguments: the current node, a lower bound, and an upper bound.

  2. Base Case: If the current node is null, it's a valid BST subtree.

  3. Validation:

    • Check if the current node's value is within the allowed range (greater than the lower bound and less than the upper bound). If not, it's not a valid BST.
    • Recursively call the helper function for the left subtree, setting the upper bound to the current node's value.
    • Recursively call the helper function for the right subtree, setting the lower bound to the current node's value.

  4. Return Value: The helper function returns true if both recursive calls return true, indicating that both subtrees are valid BSTs. Otherwise, it returns false.

  5. Initial Call: Call the helper function with the root node, setting the lower bound to Long.MIN_VALUE and the upper bound to Long.MAX_VALUE.

Explanation

The algorithm uses the properties of a BST to efficiently check its validity. By setting lower and upper bounds during recursion, we ensure that each node's value is compared against its proper range, preventing unnecessary comparisons and ensuring correctness. Using Long.MIN_VALUE and Long.MAX_VALUE for the initial call ensures that the root node is initially checked against the entire range of possible integer values.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBSTHelper(TreeNode node, long lowerBound, long upperBound) {
        if (node == null) {
            return true;
        }

        if (node.val <= lowerBound || node.val >= upperBound) {
            return false;
        }

        return isValidBSTHelper(node.left, lowerBound, node.val) &&
               isValidBSTHelper(node.right, node.val, upperBound);
    }
}

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 equal to N. In the best case (a balanced tree), H is logâ‚‚(N).