# Iterative & Recursive Java Solution with Detailed Explanation

• Iterative version:
The problem is equivalent to finding the first (smallest) element greater than p in the BST. There are 3 cases to consider:

1. `p` has a right child, then the inorder successor is the left most leaf of the right child.
2. `p` doesn't have a right child, there are 2 cases:
a) `p` is the largest value in the BST and there is no inorder successor.
b) There are nodes at upper levels with values > `p`, and we need to find the smallest of those.
We can combine `2a` and `2b` together. Use a temporary `TreeNode cur` to traverse the tree. If `cur <= p`, go right to find nodes > `p`. Else if `cur > p`, store `cur`, and go left to find smaller nodes > `p`. We stop when we reach `p`. The last stored `cur` (smallest among nodes > `p`) is our answer. If `cur` is `null`, then we can't find a node > `p`, and there is no inorder successor.
``````public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null) return null;
if (p.right != null) {
TreeNode cur = p.right;
while (cur.left != null) {
cur = cur.left;
}
return cur;
} else {
TreeNode cur = root, prev = null;
while (cur != p) {
if (cur.val > p.val) {
prev = cur;
cur = cur.left;
} else if (cur.val < p.val) {
cur = cur.right;
}
}
return prev;
}
}
}
// O(Log(n)) time, O(1) space
``````

The code above can be boiled down to a shorter one by combining case `1` & `2` above. Start from `root` and traverse down the BST.

1. If `cur.val > p.val`, store `cur` (update it if we have smaller values > `p`), then it can be two cases:
a) `cur` is an ancestor of `p` with value > `p` --> go left to find smaller values > `p`
b) `cur` is in right subtree of `p` (actually must be a right child of `p`) --> go left to find smaller values > `p`
2. If `cur.val <= p.val`, it can be:
a) `cur == p` --> go right to find values > `p`
b) `cur` is an ancestor of `p` with value < `p` --> go right to find values > `p`
``````public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode cur = root, prev = null;
while (cur != null) {
if (cur.val > p.val) {
prev = cur;
cur = cur.left;
} else {
cur = cur.right;
}
}
return prev;
}
}
``````

Recursive version (same idea): if `root.val <= p.val`, then the inorder successor must be in the right subtree. Else if `root.val > p.val`, the inorder successor could be current `root`, or some smaller value inside the left subtree.

``````public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null) {
return null;
}
if (root.val <= p.val) {
return inorderSuccessor(root.right, p);
} else {
TreeNode temp = inorderSuccessor(root.left, p);
return temp == null ? root : temp;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.