/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 as follows: for every node, all values in its left subtree are strictly less than the nodes value, and all values in its right subtree are strictly greater than the nodes value. Both left and right subtrees must also be BSTs.

Example 1

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

Output: True

Explanation: All nodes satisfy BST properties.

Example 2

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

Output: False

Explanation: Node 9 is in the left subtree of 8 but is greater than 8.

Example 3

Input: TreeNode(7, None, TreeNode(6))

Output: False

Explanation: Right child 6 is less than parent 7.

Constraints

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

Python (current runtime)

Case 1

Input: TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5), TreeNode(7)))

Expected: True

Case 2

Input: TreeNode(5, TreeNode(1), TreeNode(8, TreeNode(7), TreeNode(9)))

Expected: True

Case 3

Input: TreeNode(3, TreeNode(2, TreeNode(1), TreeNode(4)), TreeNode(5))

Expected: False

Case 4

Input: TreeNode(1, None, TreeNode(2, None, TreeNode(0)))

Expected: False