Inorder Predecessor in BST
Given the root of a BST and a node p in it, return the in-order predecessor of p: the node with the largest value smaller than p.val. If p has no predecessor, return null.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14The sorted order is 2, 4, 6, 8, 10, 12, 14. The predecessor of 6 is 4, of 8 is 6, and of 2 is null.
The predecessor is the largest value strictly smaller than p, which is the floor idea with a strict comparison, and the mirror of the successor:
- If the current node is smaller than p, it is a candidate. A larger candidate might be in its right subtree, so remember it and go right.
- If the current node is greater than or equal to p, it and its right subtree are too big, so go left.
Approach: Walk Down and Remember the Candidate
- Set
predecessor = null. - While the node exists:
- If
p.val <= node.val, go left. - Otherwise set
predecessor = nodeand go right.
- If
- Return
predecessor.
This is the successor solution with every left and right swapped and the comparisons flipped.
Code
class Solution {public:TreeNode* inorderPredecessor(TreeNode* root, TreeNode* p) {TreeNode* predecessor = nullptr;while (root != nullptr) {if (p->val <= root->val) {root = root->left;} else {predecessor = root;root = root->right;}}return predecessor;}};
Complexity
Time: O(h)
One root-to-leaf path is walked: O(log n) balanced, O(n) skewed.
Space: O(1)
Only one extra pointer is kept.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"The in-order predecessor is the largest value strictly smaller than p, which is the mirror of the successor. I walk down from the root with a stored candidate. If p's value is less than or equal to the current node, that node and its right subtree are too big, so I go left. Otherwise the current node is smaller than p, so it is a candidate, and I store it and go right to look for a larger one. When I fall off the tree, the stored candidate is the predecessor, or null if there is none. Time is O of h and space is O of one."
Next TopicBinary Search Tree Iterator