FastPrepNext Larger Value in a BST
Problems/Next Larger Value in a BST

Next Larger Value in a BST

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The round is not named in the review. It describes a resume screen, an online assessment, and then a technical interview and an HR interview for a Microsoft software engineering internship. The review gives a one-line binary-search-tree question about the next larger number, with no rules or limits.

Here x is an integer from 0 to 10^9 that need not be in the tree, and you return the smallest node value strictly greater than x, or -1 if there is none. The tree has 1 to 10^4 nodes with distinct values from 0 to 10^9 and is at most 500 levels tall, so a plain recursive solution stays within the default stack. The existing Microsoft problem Inorder Successor in a Binary Tree works on any binary tree under an O(1)-space rule, a different exercise.

Our version is about 85% the same as the reported question.

You are given the root of a binary search tree and an integer x. In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.

Return the smallest value in the tree that is strictly greater than x. If no value is greater than x, return -1. x does not have to be a value in the tree.

Function

nextLarger(root: TreeNode, x: int) → int

Examples

Example 1

root = [8,3,10,1,6,null,14,null,null,4,7,13]x = 6return = 7
root
831647101413

The tree holds 1, 3, 4, 6, 7, 8, 10, 13 and 14. The values larger than 6 are 7, 8, 10, 13 and 14, and the smallest of them is 7.

Example 2

root = [8,3,10,1,6,null,14,null,null,4,7,13]x = 7return = 8
root
831647101413

Node 7 has no right child, so the answer is not below it. The smallest value larger than 7 is the root, 8.

Example 3

root = [5,2,9]x = 9return = -1
root
529

9 is the largest value in the tree, so no value is larger and the answer is -1.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • 0 <= Node.val <= 10^9, and all node values are distinct.
  • The tree is a valid binary search tree.
  • The height of the tree (the number of nodes on the longest path from the root down to a leaf) is at most 500.
  • 0 <= x <= 10^9

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

  • Insert into a Left-Complete Binary TreeRubrik · ONSITE INTERVIEWRubrik interview questions
  • Kth Closest Element in a BSTLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
  • Shortest Path Between BST NodesGoogle · ONSITE INTERVIEWGoogle interview questions
  • Repeated BST Range Sum and AverageMeta · ONSITE INTERVIEWMeta interview questions
  • Lowest Common Ancestor in a BSTPeopleStrong · ONSITE INTERVIEWPeopleStrong interview questions
  • Delete Node in a BSTBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Validate Binary Search TreeTokopedia · ONSITE INTERVIEWTokopedia interview questions
  • Build a Perfect Binary Search TreeExpedia · ONSITE INTERVIEWExpedia interview questions
  • Check the Order of a Binary Search TreeCapital One · ONSITE INTERVIEWCapital One interview questions
  • Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions

Interview reports that mention this question

  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft 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 int nextLarger(TreeNode root, int x) {
        // Write your code here.
    }
}
Checking account…