How do you validate if a given Tree is a valid BST?

Difficulty: 5/10

binary search tree, tree traversal, recursion

BST Validation

The robust approach is to carry a valid numeric range down the tree. Each node must fall strictly between its inherited lower and upper bounds under the standard no-duplicates BST definition. Checking only the immediate left and right child is insufficient because BST violations can occur deeper in a subtree.

javascript

1
Carry lower and upper bounds to every subtree.
2
Left subtree updates the upper bound.
3
Right subtree updates the lower bound.
4
Time complexity: O(n).
5
Space complexity: O(h) due to recursion.
6
The duplicate policy must be explicitly defined.

Scenario Questions

0-2 years experience

Follow-up Questions