Validate a Binary Search Tree
Determine whether a binary tree satisfies the binary search tree property at every node, not just between direct parent-child pairs.
Given the root of a binary tree, determine whether it is a valid binary search tree (BST).
A binary tree is a valid BST if, for every node in the tree:
- Every value in that node's left subtree is strictly less than the node's own value.
- Every value in that node's right subtree is strictly greater than the node's own value.
- Both the left and right subtrees are themselves valid BSTs.
Crucially, this property must hold against every ancestor, not merely the node's immediate parent. A node can look correctly placed relative to its parent while still breaking the ordering of an ancestor higher up the tree -- such a tree is not a valid BST.
Return true if the tree is a valid BST, or false otherwise.
Example 1
Input: root = [5,3,8,2,4,7,9]
Output: true
Example 2
Input: root = [10,5,15,null,null,6,20]
Output: false
Explanation: The node with value 6 sits in the right subtree of the root (10), so it must be greater than 10 -- but 6 is not, even though 6 is locally less than its own parent (15).
Example 3
Input: root = []
Output: true
Explanation: An empty tree is trivially a valid BST.
Constraints
- The number of nodes in the tree is in the range [0, 10000].
- -2147483648 <= Node.val <= 2147483647
- All node values are unique.
Follow-up
Can you solve it using an in-order traversal instead of a bounded-range recursion?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.