AlgoLounge

Validate Binary Search Tree

medium

LeetCode 98. 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.

Examples

Example 1

Input:  root = [2,1,3]

2 / \ 1 3Output: true

Example 2

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

5 / \ 1 4 / \ 3 6Output: false The root node's value is 5, but its right child's value is 4.

Constraints

  • The number of nodes in the tree is in the range [1, 10⁴]
  • -2³¹ <= Node.val <= 2³¹ - 1

How the tests work: trees are written as level-order arrays — [1,null,2] is a root 1 with a right child 2. Your function receives real TreeNode objects.

TypeScript
Loading editor…
List of test cases (8)
Case 1
root = [2,1,3]
Case 2
root = [5,1,4,null,null,3,6]
Case 3
root = [2,2,2]
Case 4
root = [1]
Case 5
root = [5,4,6,null,null,3,7]
Case 6
root = [10,5,15,3,7,12,20]
Case 7
root = [3,1,5,null,2]
Case 8
root = [4,2,6,1,3,5,7]