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 function to traverse the tree. This function will take the current node, a minimum value (min), and a maximum value (max) as input.

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

3. Recursive Step:

   • Check if the current node's value is within the allowed range (min < node->val < max). If not, it's not a valid BST.
   • Recursively call the function for the left subtree, setting max to the current node's value.
   • Recursively call the function for the right subtree, setting min to the current node's value.
   • If both recursive calls return true, the current subtree is a valid BST.

4. Initial Call: Start the recursive process by calling the function with the root node, setting min to LONG_MIN and max to LONG_MAX.

Explanation

The algorithm works by imposing constraints on the values allowed at each node during traversal. By passing down min and max values, we enforce the BST property that all nodes in the left subtree must be less than the current node, and all nodes in the right subtree must be greater. The recursive calls ensure that this property holds for all subtrees. If at any point a node violates these constraints, the function immediately returns false.

Code

#include <iostream>
#include <limits>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBSTHelper(root, std::numeric_limits<long long>::min(), std::numeric_limits<long long>::max());
    }

private:
    bool isValidBSTHelper(TreeNode* node, long long min, long long max) {
        if (node == nullptr) 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 could be N, resulting in O(N) space complexity. In the best case (a balanced tree), H would be log(N), resulting in O(log N) space complexity.