LeetCode #98.Validate Binary Search Tree

Time Complexity: O(n)

We visit every node exactly once
At each node, we do constant work (a few comparisons)
So total work = O(n) where n = number of nodes

Space Complexity: O(h) → where h = height of the tree

This comes from the recursion stack (call stack).
Best case: O(log n)
→ Balanced tree (height ≈ log n)
→ Maximum stack depth = log n
Worst case: O(n)
→ Completely skewed tree (like a linked list)
→ Stack depth = n (all nodes on one side)

class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode node, Integer lower, Integer upper) {
        // Empty tree is valid
        if (node == null) {
            return true;
        }

        // Check bounds
        if (lower != null && node.val <= lower) return false;
        if (upper != null && node.val >= upper) return false;

        // Left subtree: all values must be < node.val  → tighten the upper bound
        // Right subtree: all values must be > node.val → tighten the lower bound
        if (!helper(node.left, lower, node.val)) return false;
        if (!helper(node.right, node.val, upper)) return false;

        return true;

    }
}