98. Validate Binary Search Tree - Detailed Explanation

Problem Statement

Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST). A valid BST satisfies:

• 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 left and right subtrees must also be BSTs.

Examples

    2
   / \
  1   3

• Input: [2,1,3]
• Output: true

    5
   / \
  1   4
     / \
    3   6

• Input: [5,1,4,null,null,3,6]
• Output: false
• Explanation: 3 is in the right subtree of 5 but less than 5

Constraints

• The number of nodes in the tree is in the range [1, 10⁴].
• –2³¹ ≤ Node.val ≤ 2³¹−1

Hints

1. An in‑order traversal of a BST visits nodes in strictly increasing order.
2. You can recursively verify each node’s value against allowed (min, max) bounds passed down from its ancestors.
3. Be careful with integer limits when using bounds.

Approaches

In‑Order Traversal (Recursive)

Perform a DFS in‑order (left → node → right), keeping track of the previously visited value. If at any point the current node’s value is ≤ the previous value, it violates the BST property.

Steps

1. Initialize prev = None (or -∞).
2. Traverse left subtree.
3. When visiting a node, compare node.val to prev. If prev is not None and node.val ≤ prev, return false.
4. Update prev = node.val.
5. Traverse right subtree.
6. If no violations, return true.

Step‑by‑Step

For tree [5,1,4,null,null,3,6]:

• In‑order visits 1 → 5 → 3 → …
• At 3, compare to prev=5: 3 ≤ 5 → invalid.

Range‑Check Recursion

At each node, carry down a valid open interval (low, high) that the node’s value must lie within.

1. Start with (low, high) = (−∞, +∞).
2. For node with value v, check low < v < high.
3. Recurse left with (low, v).
4. Recurse right with (v, high).
5. If any check fails, return false.

Step‑by‑Step

For the invalid tree:

• Root=5 in (−∞,∞) → OK
• Right child=4 must be in (5,∞). 4 ≤ 5 → invalid.

Iterative In‑Order with Stack

Same idea as recursive in‑order, but use an explicit stack to traverse. Pop until leftmost, then process nodes and push right children.

Complexity Analysis

• Time: O(n) — each node visited once
• Space: O(n) worst‑case recursion stack or explicit stack

Python Code