Inorder Predecessor in a BST
Updated
Problem statement
You are given the root of a binary search tree and an integer target. All node values are different. For every node, each value in its left subtree is smaller than the node's value and each value in its right subtree is larger. target is the value of one node in the tree; call it the target node.
Return the value of the node that comes just before the target node in inorder, which is the order from smallest value to largest. If the target node holds the smallest value in the tree, nothing comes before it: return -1.
Function
inorderPredecessor(root: TreeNode, target: int) → intExamples
Example 1
root = [20,10,30,5,15,null,40]target = 20return = 15In order, the values are 5, 10, 15, 20, 30, 40. The value just before 20 is 15. In the tree, 15 is the rightmost node of 20's left subtree.
Example 2
root = [20,10,30,5,15,null,40]target = 30return = 20Node 30 has no left child, so the node before it is above it. Going up from 30, the first ancestor that 30 is to the right of is the root 20. In order, 20 is indeed just before 30.
Example 3
root = [8,null,12,9]target = 8return = -1The tree is 8 with right child 12, and 12 has left child 9. In order the values are 8, 9, 12. 8 is the smallest value, so nothing comes before it and the answer is -1.
Constraints
- The number of nodes is between
1and2000. 0 <= node.val <= 10^5- No two nodes have the same value, and the tree follows the binary search tree rule.
targetis the value of a node in the tree.- The tree does not have to be balanced. It can be a single chain, so its height can equal its number of nodes.
More Nutanix Phone Screen questions
- Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
- Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
- Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
- Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
- Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
- Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
- Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
- Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
- K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
- Odd Numbers Up and BackPHONE SCREEN · Seen Jan 2019
Similar questions at other companies
- Add All Larger Values in a BSTAdobe · PHONE SCREENAdobe interview questions
- Shortest Path Between BST NodesGoogle · ONSITE INTERVIEWGoogle interview questions
- Validate Binary Search TreeTokopedia · ONSITE INTERVIEWTokopedia interview questions
- Check the Order of a Binary Search TreeCapital One · ONSITE INTERVIEWCapital One interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- House Robber IIIOkta · PHONE SCREENOkta interview questions
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Validate Binary Search TreeKotak Mahindra Bank · PHONE SCREENKotak Mahindra Bank interview questions
- House Robber IIIGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions