Check the Order of a Binary Search Tree
Updated
Problem statement
A binary search tree lets you find any value by starting at the root and turning left for smaller values and right for larger ones. For that to work, the order has to hold for whole subtrees, not only for children: nothing below a node on its left side may be greater than or equal to it, and nothing below it on its right side may be less than or equal to it.
Answer true when the tree at root keeps this order everywhere and false when it does not.
Function
isValidBST(root: TreeNode) → booleanExamples
Example 1
root = [-5,-20,40,null,-9,0]return = trueReading the tree from left to right gives -20, -9, -5, 0, 40: always increasing. Every node has only smaller values on its left and larger values on its right, so the tree is valid.
Example 2
root = [100,50,150,null,80,null,null,45]return = falseThe root is not the problem here: 45 is smaller than 100, and it is smaller than its parent 80, as a left child should be. The broken bound comes from 50: 45 is under the right child of 50, so it would have to be larger than 50.
Example 3
root = [1,null,4,4]return = falseThe two 4s tie. Equal values are not allowed, wherever they appear, so the tree is not valid.
Constraints
- The tree has between
1and500nodes. -2^31 <= Node.val <= 2^31 - 1
More Capital One Onsite Interview questions
- Digit-Coded Card ValidationONSITE INTERVIEW · Seen Nov 2026
- Sort ColorsONSITE INTERVIEW · Seen Oct 2026
- Virtual Card Transaction ValidatorONSITE INTERVIEW · Seen Oct 2026
- Banking System with Top ActivityONSITE INTERVIEW · Seen Sep 2026
- Transaction Event StoreONSITE INTERVIEW · Seen Jul 2026
- Shortest Path in an Unweighted GraphONSITE INTERVIEW · Seen Jul 2026
- Duplicate Transactions Within 60 SecondsONSITE INTERVIEW · Seen May 2026
- LRU CachePHONE SCREEN · ONSITE INTERVIEW · Seen May 2026
- Cashback TrackerONSITE INTERVIEW · Seen Nov 2025
- Reverse a StringOA · ONSITE INTERVIEW · Seen Oct 2025
Similar questions at other companies
- Shortest Path Between BST NodesGoogle · ONSITE INTERVIEWGoogle interview questions
- Validate Binary Search TreeTokopedia · ONSITE INTERVIEWTokopedia interview questions
- Add All Larger Values in a BSTAdobe · PHONE SCREENAdobe interview questions
- Inorder Predecessor in a BSTNutanix · PHONE SCREENNutanix interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP 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
- Insert into a Left-Complete Binary TreeRubrik · ONSITE INTERVIEWRubrik interview questions
Capital One interview experiences
- Capital One Experienced Engineer Power Day and OA: 6 Experiences
- Capital One New Grad OA Questions: 14 Experiences (Part 2 of 2)
- Capital One TDP Agentic Round (AI Coding): 7 Experiences
- Capital One SWE Power Day, Level Not Reported: 6 Experiences
- Capital One TIP Intern OA and Power Day: 13 Experiences
- Capital One TDP Agentic Power Day: 25 Experiences (Part 1 of 2)