Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST requires all nodes in the left subtree to be strictly less than the node value and all nodes in the right subtree to be strictly greater. This rule must hold for every subtree.

Function signature

func IsValidBST(root *TreeNode) bool

Inputs / outputs

• root: root of the tree.
• Return: true if the tree is a valid BST, else false.

Example

    2
   / \
  1   3
Output: true

    5
   / \
  1   4
     / \
    3   6
Output: false (the 3 is in the right subtree of 5 but smaller than 5)

Constraints

• 0 <= number of nodes <= 100_000
• node values fit in 32-bit signed int

Core idea (near-solution)

Use DFS with value bounds. Each node must satisfy low < node.Val < high, where the bounds come from all ancestors, not just the parent.

Invariant: when you enter a node, all values in this subtree must fall strictly between low and high.

Algorithm (step-by-step)

1. If root is nil, it is valid.
2. Recurse with bounds (-inf, +inf).
3. At each node:
   • If Val is outside bounds, return false.
   • Recurse left with (low, Val) and right with (Val, high).
4. Return true only if both subtrees are valid.

Correctness sketch

• Invariant: when you enter a node, all values in this subtree must fall strictly between low and high.
• Each node is checked against valid (lo, hi) bounds for its subtree.
• Bounds are tightened when descending, preserving the BST invariant.
• Any violation is detected, otherwise all nodes satisfy BST ordering.

Trace (hand walkthrough)

Example input:
    2
   / \
  1   3
Output: true

    5
   / \
  1   4
     / \
    3   6
Output: false (the 3 is in the right subtree of 5 but smaller than 5)

Walk:
- tree1 inorder: 1,2,3 (strictly increasing) -> true
- tree2: visit 5 with right child 4; right-left is 3 < 5 -> violates bounds -> false

Pitfalls to avoid

• Using non-strict inequalities (<= or >=).
• Using int bounds that can overflow; prefer int64.

Complexity

• Time: O(n)
• Extra space: O(h) for recursion depth.

Implementation notes (Go)

• Pass lower/upper bounds as int64 to avoid overflow.
• Use strict inequalities: lo < val < hi.