On this page

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 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

The 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

  1. Set predecessor = null.
  2. While the node exists:
    • If p.val <= node.val, go left.
    • Otherwise set predecessor = node and go right.
  3. 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