# Share my Java recursive solution

• Just want to share my recursive solution for both getting the successor and predecessor for a given node in BST.

Successor

``````public TreeNode successor(TreeNode root, TreeNode p) {
if (root == null)
return null;

if (root.val <= p.val) {
return successor(root.right, p);
} else {
TreeNode left = successor(root.left, p);
return (left != null) ? left : root;
}
}
``````

Predecessor

``````public TreeNode predecessor(TreeNode root, TreeNode p) {
if (root == null)
return null;

if (root.val >= p.val) {
return predecessor(root.left, p);
} else {
TreeNode right = predecessor(root.right, p);
return (right != null) ? right : root;
}
}``````

• Very nice! I wish I had thought of that.

Here's just a small variation, mainly using a loop instead of the recursion-to-right:

``````public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
while (root != null && root.val <= p.val)
root = root.right;
if (root == null)
return null;
TreeNode left = inorderSuccessor(root.left, p);
return (left != null && left.val > p.val) ? left : root;
}
``````

And another:

``````public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
while (root != null && root.val <= p.val)
root = root.right;
TreeNode left = root == null ? null : inorderSuccessor(root.left, p);
return (left != null && left.val > p.val) ? left : root;
}
``````

• Thanks Stefan, actually I learn a lot from your solutions!

• return (left != null && left.val > p.val) ? left : root
could be simplified to
return (left != null) ? left : root

• This post is deleted!

• yes, just find out the left-most node, because this is BST

• Thank you guys!

• left.val > p.val this can be ignored.

• @Jinx_boom Thanks, you're right.

Judging by a Ruby solution I wrote based on this (posted now), I apparently noticed it but then forgot about it... strange.

• Can anyone help to explain when the predecessor() can return a not null value?

• The solution is clear, but it seems it cannot detect whether p is inside of tree or not. And this seems cannot deal with tree with duplicate value and p's value is one of the duplicate.

• This solution is nice, but I still cannot understand `return (left != null) ? left : root;` Can anyone explain it? Thank you!

• Hi @xietao0221, let's take the successor for example, basically we always want to find `p`'s closest node (in inorder traversal) and the node's value is larger than `p`'s value, right? That node can either be `p`'s parent or the smallest node in `p`' right branch.

When the code runs into the else block, that means the current root is either `p`'s parent or a node in `p`'s right branch.

If it's `p`'s parent node, there are two scenarios: 1. `p` doesn't have right child, in this case, the recursion will eventually return null, so `p`'s parent is the successor; 2. `p` has right child, then the recursion will return the smallest node in the right sub tree, and that will be the answer.

If it's `p`'s right child, there are two scenarios: 1. the right child has left sub tree, eventually the smallest node from the left sub tree will be the answer; 2. the right child has no left sub tree, the recursion will return null, then the right child (root) is our answer.

I guess it's hard to understand unless you draw different scenarios out. :)

• Thank you for your reply, your explanation is perfect, finally I know these four scenarios. Thank you so much!!!
BTW, you'd better add this part of words on your solution.

• @xietao0221 yes, I agree with you. If p is not in the BST, but the BST has nodes whose values are larger than p's, this solution still has a not-null return.

• do you consider the cases where there are duplicates (let's say every node has the same value, but p points to the left most one. your program will keeps going to the right and return null.) in the case below, a root has a left and right child, p points to the left child, we should return root, yet your program will return null, right?
-------------2 <-root
p------>2-----2
and the other case is there is no node p in the tree (you algorithm will return some node, but if p is not in the tree, I think we should return null, right?)
Thanks

• Hi @jeantimex :

I feel that there is a small bug in your code:

If the BST has duplicate nodes and the given node is P which is to the left of the current root (in a recursive call) but root.val == p.val, then in this case your code, will incorrectly return successor(root.right, p).

Correct me if I'm wrong?

• Awesome algorithm! For me took a while to grasp the idea. Here is my less sexy but probably with a little but less magic version derived from your code...

``````TreeNode lastLeftParent;

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
lastLeftParent = null;
successor(root, p);
return lastLeftParent;
}

public void successor(TreeNode root, TreeNode p) {
if (root != null) {
if (p.val >= root.val) successor(root.right, p);
else {
lastLeftParent = root;
successor(root.left, p);
}
}
}``````

• ``````    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null) return null;

if(root.val <= p.val){
return inorderSuccessor(root.right, p);
} else {
// if (left == null) means on the left nodes of this root, no any node has value between this root and the target P.
// so return this root, otherwise recusively go to root.left.
TreeNode left = inorderSuccessor(root.left, p);
return left == null ? root: left;
}
}``````

• This post is deleted!

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