### Question

Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

### Solution

**If current node have a right child**, return the leftmost leaf of right child.**If current node have no right child**:If current is parent’s left child, then return parent node.

If current is parent’s right child, look all the way up until find a right-turning parent.

If all parent is not right-turning. Return null.

### Code

**written by me**

```
public static TreeNode inorderSucc(TreeNode e) {
if (e == null)
return null;
if (e.right != null) {
TreeNode p = e.right;
while (p.left != null) {
p = p.left;
}
return p;
} else {
TreeNode p = e.parent;
while (p != null && p.right == e) {
e = p;
p = e.parent;
}
return p;
}
}
```