Validate Binary Search Tree

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

A valid BST is defined as follows:

• 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 the left and right subtrees must also be binary search trees.

Function signature

func IsValidBST(root *TreeNode) bool

TreeNode definition

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Examples

Example 1:

Input:
    2
   / \
  1   3

Output: true
Explanation: Left child (1) < root (2) < right child (3). Valid BST.

Example 2:

Input:
    5
   / \
  1   4
     / \
    3   6

Output: false
Explanation: The node with value 3 is in the right subtree of 5, but 3 < 5.

Example 3:

Input:
    5
   / \
  4   6
     / \
    3   7

Output: false
Explanation: 3 is in the right subtree of 5, violating the BST property.

Example 4:

Input: nil (empty tree)
Output: true
Explanation: An empty tree is a valid BST.

Constraints

• The number of nodes in the tree is in the range [0, 10000]
• -2^31 <= Node.val <= 2^31 - 1

Hints

1. The naive approach of checking left.val < root.val < right.val is incorrect. Why?
2. Every node must be within a valid range. How do you pass this range down?
3. Alternative: What order does inorder traversal give for a BST?

Notes

• This problem trips up many candidates who only check immediate children.
• Two approaches work: (1) pass valid range down, or (2) check inorder gives strictly increasing sequence.