Reference: LeetCode
Difficulty: Medium
My Post: Java Solution + Explanation (Recursion & Iteration)
Problem
Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node
p
is the node with the smallest key greater thanp.val
.
Note:
- If the given node has no in-order successor in the tree, return
null
. - It’s guaranteed that the values of the tree are
unique
.
Example:
1 | Input: root = [2,1,3], p = 1 |
Analysis
Methods:
x
is the current node;p
is the target node.
- Recursion
- If
p
is in the left subtree, the successor could bex
orsuccessor(x.left)
. It means thatx
is a possible candidate. It turns to be a real successor when the return value ofsuccessor(x.left)
equalsnull
. - If
p
is in the right subtree, the successor must be in the right subtree if it exists. - If
p
is found, we still go to right subtree to find its successor if it exists. - The base case is when
x
reachesnull
. - Time: $O(h)$
- Space: $O(h)$
- If
- Iteration
- We use a variable
succ
to record the successor, which is initiallynull
. - If
p.val
is less thanx.val
, it needs to go left, and we need to updatesucc
. - If
p.val
is greater than or equal tox.val
:greater than
: Just go right.x.left
andx
couldn’t be the successor.equal to
: Just go right too. In the next round,p.val
will be less thanx.val
, it will set thesucc
to the would-be right childx
.
- Time: $O(h)$
- Space: $O(1)$
- We use a variable
Code
Test Case:
1 | [2,1,3] p = 1 |
Recursion
1 | public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { |
Predecessor:
1 | public TreeNode inorderPredecessor(TreeNode root, TreeNode p) { |
Iteration
1 | public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { |
Ceil
Code: algs4 - BST.java
The idea is also applied to ceil
operation:
1 | public Key ceil(Key key) { |