FastPrepCheck the Order of a Binary Search Tree
Problems/Check the Order of a Binary Search Tree

Check the Order of a Binary Search Tree

Capital One logoCapital One● MediumINTERNNEW GRADONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Seven Capital One reports from 2017 and early 2018 name the task of checking that a binary search tree is valid. Six are from intern candidates and one is from a new graduate. One report frames the input as a single starting node rather than a whole tree.

Here the tree comes in level order with up to 500 nodes holding any 32-bit values. The order must be strict, so equal values make the tree invalid. These are our choices.

Our version is about 95% the same as the reported questions.

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) → boolean

Examples

Example 1

root = [-5,-20,40,null,-9,0]return = true
root
-5-20-9400

Reading 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 = false
root
100508045150

The 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 = false
root
144

The two 4s tie. Equal values are not allowed, wherever they appear, so the tree is not valid.

Constraints

  • The tree has between 1 and 500 nodes.
  • -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)
All Capital One interview questionsSee Capital One hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        // Write your code here.
    }
}
Checking account…