You are given root, the root of a non-empty binary tree.
Return true if it is a valid binary search tree, and false otherwise. In a valid binary
search tree, for every node:
- every value in its left subtree is strictly smaller than the node's value, and
- every value in its right subtree is strictly larger.
So no value may appear twice, and the rule covers whole subtrees, not only a node's children.
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- root = [8, 4, 12, 2, 6, 10, 14]
- Output
- true
Example 2
- Input
- root = [8, 4, 12, 2, 6, 7, 14]
- Output
- false
Constraints
- The tree holds 1 to 1000 nodes.
- Every value is between −2³¹ and 2³¹ − 1.
Show the pattern
Trees
Each node must fit between bounds set by all of its ancestors, not just its parent. Passing those bounds down a depth-first recursion checks every node against everything above it.
See trees in a visualiserShow the approach
Give each node the open range (low, high) its value must lie in. The root's range has no
bounds. A node is fine when low < val < high; its left subtree must then lie in (low, val)
and its right subtree in (val, high). Recurse, and the tree is valid when every node is fine.
An empty subtree is always fine.
The bounds carry every ancestor's constraint down at once, so a node deep in the tree is checked against all the nodes above it. (An in-order traversal that checks the values strictly increase works too.)
Time: O(n) · Space: O(h) for the recursion, h the tree's height