Validate Binary Search Tree

Validate Binary Search Tree Overview
The "Validate Binary Search Tree" problem (LeetCode 98) asks you to check if a given binary tree is a valid BST using DFS traversal. It matches LinkedIn interview contexts with tags Tree, DFS, BST, and Binary Tree, focusing on recursive validation.[1][9]

Full Problem Statement

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.[9][1]

Input/Output Examples

Example 1: Valid BST

Input: root =[2][3][1] 2 / \ 1 3
Output: true

Example 2: Invalid BST (right subtree violation)

Input: root = [5,1,4,null,null,3,6]
5 / \ 1 4 / \ 3 6
Output: false

Example 3: Single Node (Valid)

Input: root =[5] 5
Output: true

Example 4: Empty Tree (Valid)

Input: root = []
Output: true

Example 5: Invalid Due to Duplicate/Non-Strict

Input: root = [5,1,5,null,null,3,6] (duplicate 5)
Output: false (strictly less/greater required).[1]

Constraints

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

Note: Node values can be duplicates, but valid BST requires strict inequality (< and >, not <= or >=).[3][1]