MediumTreesAI interview only
Validate Binary Search Tree
Asked atamazongooglemicrosoftbloombergapple
01 · Problem
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
02 · Examples
Example 01
2 / \ 1 3
Input
root = [2,1,3]
Output
true
Node 1 < root 2 (valid left child). Node 3 > root 2 (valid right child). Both subtrees are valid BSTs.
Example 02
5
/ \
1 4
/ \
3 6Input
root = [5,1,4,null,null,3,6]
Output
false
The right child of the root has value 4, which is less than the root value 5. This violates the BST property.
03 · Constraints
- 01The number of nodes in the tree is in the range [1, 104].
- 02-231 <= Node.val <= 231 - 1
04 · Optimal complexity
- Time
- O(n)
- Space
- O(h)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.