/98. Validate Binary Search Tree

98. Validate Binary Search Tree

Medium

Trees35.5% acceptance

Given the root node of a binary tree, determine whether the tree satisfies the properties of a binary search tree (BST). A BST is defined such that for every node, all values in its left subtree are strictly less than the nodes value, all values in its right subtree are strictly greater than the nodes value, and both subtrees are themselves BSTs.

Example 1

Input: TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(12), TreeNode(20)))

Output: True

Explanation: All left subtree values are less than 10, all right subtree values are greater than 10, and subtrees are BSTs.

Example 2

Input: TreeNode(8, TreeNode(3, None, TreeNode(6)), TreeNode(10, None, TreeNode(9)))

Output: False

Explanation: Node 9 is in the right subtree of 8 but less than 10, violating BST property.

Constraints

1 <= number of nodes <= 10_000
-2_147_483_648 <= node value <= 2_147_483_647
Input is a binary tree represented by TreeNode objects

Python (current runtime)

Case 1

Input: TreeNode(7, TreeNode(2), TreeNode(9))

Expected: True

Case 2

Input: TreeNode(6, TreeNode(4, TreeNode(3), TreeNode(5)), TreeNode(8, None, TreeNode(7)))

Expected: False

Case 3

Input: TreeNode(1)

Expected: True

Case 4

Input: TreeNode(15, TreeNode(10, TreeNode(5), TreeNode(12)), TreeNode(20, None, TreeNode(25)))

Expected: True