Next Larger Value in a BST
Updated
Problem statement
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) → intExamples
Example 1
root = [8,3,10,1,6,null,14,null,null,4,7,13]x = 6return = 7The 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 = 8Node 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 = -19 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