Next Larger Node in a BST
Updated
Problem statement
Given the root of a binary search tree and the value target of one of its nodes, return the value of the node that comes right after it in sorted order, that is, the smallest value in the tree that is larger than target.
If target is the largest value in the tree, return -1.
Function
nextLarger(root: TreeNode, target: int) → intExamples
Example 1
root = [41,17,63,9,26,55,78,null,13,22,34,null,58]target = 34return = 41Node 34 has no right child. Going up, 34 is in the left subtree of 41 (through 17 and 26), so 41 is the smallest larger value. The sorted values are 9, 13, 17, 22, 26, 34, 41, 55, 58, 63, 78, and 41 comes right after 34.
Example 2
root = [41,17,63,9,26,55,78,null,13,22,34,null,58]target = 17return = 22Node 17 has a right subtree (26 with children 22 and 34). The smallest value there is 22, found by going right once and then left as far as possible.
Example 3
root = [41,17,63,9,26,55,78,null,13,22,34,null,58]target = 78return = -178 is the largest value in the tree, so nothing comes after it. The answer is -1.
Constraints
- The tree has
1to1000nodes. 1 <= Node.val <= 10^5, and all values are different- The tree is a binary search tree: for every node, all values in its left subtree are smaller and all values in its right subtree are larger.
targetis the value of a node in the tree
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- AVL Insertion and RotationsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Delete Node in a BSTBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Node in a BSTTokopedia · PHONE SCREENTokopedia interview questions
- Inorder Predecessor in a BSTNutanix · PHONE SCREENNutanix interview questions
- Lowest Common Ancestor in an Inserted BSTAmazon · PHONE SCREEN
- 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
Interview reports that mention this question
Adobe interview experiences
- Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
- Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
- Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
- Adobe New Grad MTS Interview Questions: 7 Experiences
- Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)