Leetcode - 98. Validate Binary Search Tree

🌲 Two Elegant Ways to Validate a Binary Search Tree (BST) in JavaScript

A Binary Search Tree (BST) is a binary tree where:

• All nodes in the left subtree are less than the node.
• All nodes in the right subtree are greater than the node.
• These rules apply recursively to every node in the tree.

Let’s walk through two clean approaches to validate if a binary tree is a BST — using recursion and in-order traversal.

---

✅ Approach 1: Recursion with Min/Max Bounds

🧠 Intuition

As we recursively visit each node, we carry down the range of valid values.
For example:

• For left children: the value must be < current node
• For right children: the value must be > current node

We keep narrowing the valid range (min, max) as we go deeper.

📦 Code

var isValidBST = function (root) {
    function validate(node, min, max) {
        if (!node) return true;

        if ((min !== null && node.val <= min) || (max !== null && node.val >= max)) {
            return false;
        }

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

    return validate(root, null, null);
};

⏱️ Time Complexity

• O(n): We visit every node once.

📦 Space Complexity

• O(h): h is the height of the tree (stack depth during recursion).

  • O(log n) for balanced tree, O(n) for skewed tree.

---

✅ Approach 2: In-order Traversal Check

🧠 Intuition

In-order traversal of a valid BST gives a strictly increasing sequence.
So we do an in-order traversal and ensure that each node value is greater than the last one visited.

📦 Code

var isValidBST = function (root) {
    let prev = null;

    function inorder(node) {
        if (!node) return true;

        if (!inorder(node.left)) return false;

        if (prev !== null && node.val <= prev) {
            return false;
        }

        prev = node.val;

        return inorder(node.right);
    }

    return inorder(root);
};

⏱️ Time Complexity

• O(n): We traverse each node once.

📦 Space Complexity

• O(h): Recursion stack; same as above.

---

🧠 When to Use Which?

Scenario	Use Approach
You want to validate value ranges	Min/Max (Approach 1)
You want a short & elegant check	In-order (Approach 2)
Interview setting (quick & clean)	In-order is great for impressing 😄

---

🧪 Bonus Tip: No Duplicates!

Both methods assume that no duplicate values are allowed in the BST.
That's why we check for strictly less/greater, not <= or >=.

---