Validate Binary Search Tree
Updated
Problem statement
You are given the root of a binary tree. Return true if it is a valid binary search tree, and false otherwise.
A binary search tree is valid when, for every node:
- every value in the node's left subtree is strictly smaller than the node's value, and
- every value in the node's right subtree is strictly larger than the node's value.
So two nodes with the same value can never both be in a valid tree.
Function
isValidBST(root: TreeNode) → booleanExamples
Example 1
root = [8,3,10,1,6,null,14]return = trueEvery value in the left subtree of 8 (3, 1, 6) is smaller than 8, and every value in its right subtree (10, 14) is larger. The same holds at 3 (1 on the left, 6 on the right) and at 10 (14 on the right). So the tree is a binary search tree.
Example 2
root = [8,3,10,1,9]return = falseNode 9 is the right child of 3, which is fine for node 3 because 9 > 3. But 9 is also in the left subtree of the root 8, and 9 is not smaller than 8. So the tree is not a binary search tree.
Example 3
root = [5,5]return = falseThe left child has the same value as the root. Values in a left subtree must be strictly smaller, so the answer is false.
Constraints
- The number of nodes in the tree is in the range
[1, 2000]. -2^31 <= Node.val <= 2^31 - 1- The height of the tree (the number of nodes on the longest path from the root down to a leaf) is at most
500.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Maximum Sum Among Longest Root-to-Leaf PathsAmazon · ONSITE INTERVIEW
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Onion-Peel Layers of a Binary TreeeBay · ONSITE INTERVIEWeBay interview questions
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEWUber interview questions
- Lowest Common Ancestor in a Rooted TreeKarat · ONSITE INTERVIEWKarat interview questions