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 minimum value (min), and a maximum value (max).

  2. Base Case: If the current node is null, it's a valid subtree, so we return true.

  3. Validation:

    • Check if the current node's value is within the allowed range (min < node.val < max). If not, it's not a valid BST, so return false.
    • Recursively check the left subtree with an updated max (the current node's value).
    • Recursively check the right subtree with an updated min (the current node's value).

  4. Return Value: If all checks pass, the entire subtree rooted at the current node is a valid BST, so return true.

Explanation

The recursive approach efficiently checks the BST property. By passing min and max values, we constrain the possible range of values for each subtree. This prevents us from needing to traverse the entire tree for each node to validate the BST property. The base case handles empty subtrees, ensuring the function terminates correctly. The validation step ensures each node's value conforms to the BST definition, and recursive calls ensure that the subtrees also satisfy the definition.

Code

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool IsValidBST(TreeNode root) {
        return IsValidBSTHelper(root, long.MinValue, long.MaxValue);
    }

    private bool IsValidBSTHelper(TreeNode node, long min, long max) {
        if (node == null) return true;

        if (node.val <= min || node.val >= max) return false;

        return IsValidBSTHelper(node.left, min, node.val) && 
               IsValidBSTHelper(node.right, node.val, max);
    }
}

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).