Validate BST

Problem Statement

Check whether a binary tree is a valid Binary Search Tree (BST).

Example: Input: [2,1,3] → Output: true

Approach 1: Recursive Inorder Traversal

Explanation: BST inorder traversal must produce sorted values.

Time Complexity: O(n)

Space Complexity: O(h)

prev = -∞
function inorder(node):
    if node == NULL: return true
    if not inorder(node.left): return false
    if node.val <= prev: return false
    prev = node.val
    return inorder(node.right)

💡 Think: Inorder must be strictly increasing; track prev and fail on any non-increase.

Approach 2: Recursion with Min/Max

Explanation: Each node must satisfy min < val < max constraints.

Time Complexity: O(n)

Space Complexity: O(h)

function isBST(node, min, max):
    if node == NULL: return true
    if node.val <= min or node.val >= max: return false
    return isBST(node.left, min, node.val) and isBST(node.right, node.val, max)

💡 Think: Each node must satisfy (min < val < max); tighten bounds as you descend.

Solve on LeetCode