Problem
Validate Binary Search Tree
Medium- trees
- binary-search-tree
Decide whether the binary tree root is a valid binary search tree. Every node must be larger than every value in its left subtree and smaller than every value in its right subtree, and this has to hold at every node, not only at the root. Equal values are never allowed, so a duplicate makes the tree invalid.
Trees in this problem are written as level-order arrays: the root first, then each level from left to right. null marks a missing child, and a missing child has no entries beneath it. Trailing nulls are omitted.
- Input
root = [8, 3, 10, 1, 6, null, 14]- Output
true- Explanation
the left side of 8 holds 3, 1 and 6, all smaller than 8, and the right side holds 10 and 14, both larger. The same rule holds at 3 and at 10.
- Input
root = [10, 5, 15, null, null, 6, 20]- Output
false- Explanation
every node fits next to its own children, but 6 sits in the right subtree of 10 and is smaller than 10.
- Input
root = [2, 2, 2]- Output
false- Explanation
a child equal to its parent breaks the strict ordering.
Tab indents. Press Esc, then Tab to leave the editor.
Run your code to see every test here. Nothing is submitted or recorded.