294. 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 strictly less than the node's key.
• The right subtree of a node contains only nodes with keys strictly greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Validate whether a binary tree satisfies the BST property. A common mistake is to only check parent-child relationships — you must ensure all ancestors are respected.

Requirements

1. Basic Functionality

• Return true if the tree is a valid BST, false otherwise
• An empty tree is a valid BST
• No duplicate values allowed (strict inequality)

Example Usage

// Tree: [2,1,3]  →  true (valid BST)
// Tree: [5,1,4,null,null,3,6]  →  false (4's left child 3 < 5's right child)

Real-World Context

• Database indexing: B-trees and BSTs power database indexes — validation ensures correctness
• File systems: Directory trees often maintain sorted order for efficient lookup
• Auto-complete: Trie structures with BST-like ordering for suggestion ranking