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:

- The left subtree of a node contains only nodes with keys **strictly less than** the node's key.

- The right subtree contains only nodes with keys **strictly greater than** the node's key.

- Both subtrees must also be valid BSTs.

Input: root = [2,1,3]

Output: true

1 < 2 < 3, valid BST.

Input: root = [5,1,4,null,null,3,6]

Output: false

Node 4 is in the right subtree of 5, but 4 < 5.

Time

O(n)

Space

O(h)

#1 Valid BST

Input: [2,1,3]

Expected: true

#2 Invalid BST

Input: [5,1,4,null,null,3,6]

Expected: false

#3 Single node

Input: [1]

Expected: true

#4 Subtree violation

Input: [5,4,6,null,null,3,7]

Expected: false