Iterative version:

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

`p`

has a right child, then the inorder successor is the left most leaf of the right child.`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.

- 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`

- 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;
}
}
}
```