**Objective:** **– **Given a Binary Search Tree, Find predecessor and Successor of a given node.

*What is Predecessor and Successor :*

*When you do the inorder traversal of a binary tree, the neighbors of given node are called Predecessor(the node lies behind of given node) and Successor (the node lies ahead of given node).*

**Example:**

**Approach:**

**Say you have to find the inorder predecessor and successor node 15.**

- First compare the 15 with root (25 here).
- 25>15 => successor = 25, make recursive call to root.left.(Why do we do it , is explained at step 3).
- New root which is = 15, now stop making recursive calls.
- Now successor will be the left most node in right subtree of which has the root 18 here. So the left most element and successor will be 19. (What if 15 doesn’t have a right subtree, then successor of 15 will be the parent of it, and that is why we set parent as successor in step1).
- Now predecessor will be the right most node in left subtree which has the root 10 here. but 10 doesn’t have right child.
- For the same reason when node<root then make predecessor = root and make a recursive call to the root.right.

**Complete Code:**

public class InorderSuccessorPredecessor { | |

static int successor, predecessor; | |

public void successorPredecessor(Node root, int val) { | |

if (root != null) { | |

if (root.data == val) { | |

// go to the right most element in the left subtree, it will the | |

// predecessor. | |

if (root.left != null) { | |

Node t = root.left; | |

while (t.right != null) { | |

t = t.right; | |

} | |

predecessor = t.data; | |

} | |

if (root.right != null) { | |

// go to the left most element in the right subtree, it will | |

// the successor. | |

Node t = root.right; | |

while (t.left != null) { | |

t = t.left; | |

} | |

successor = t.data; | |

} | |

} else if (root.data > val) { | |

// we make the root as successor because we might have a | |

// situation when value matches with the root, it wont have | |

// right subtree to find the successor, in that case we need | |

// parent to be the successor | |

successor = root.data; | |

successorPredecessor(root.left, val); | |

} else if (root.data < val) { | |

// we make the root as predecessor because we might have a | |

// situation when value matches with the root, it wont have | |

// left subtree to find the predecessor, in that case we need | |

// parent to be the predecessor. | |

predecessor = root.data; | |

successorPredecessor(root.right, val); | |

} | |

} | |

} | |

public static void main(String args[]) { | |

Node root = new Node(20); | |

root.left = new Node(10); | |

root.right = new Node(30); | |

root.left.left = new Node(5); | |

root.left.left.right = new Node(7); | |

root.left.right = new Node(15); | |

root.right.left = new Node(25); | |

root.right.right = new Node(35); | |

root.left.right.left = new Node(13); | |

root.left.right.right = new Node(18); | |

InorderSuccessorPredecessor i = new InorderSuccessorPredecessor(); | |

i.successorPredecessor(root, 10); | |

System.out.println("Inorder Successor of 10 is : " + successor | |

+ " and predecessor is : " + predecessor); | |

i.successorPredecessor(root, 30); | |

System.out.println("Inorder Successor of 30 is : " + successor | |

+ " and predecessor is : " + predecessor); | |

} | |

} | |

class Node { | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

left = null; | |

right = null; | |

} | |

} |

**Output**:

Inorder Successor of 10 is : 13 and predecessor is : 7 Inorder Successor of 30 is : 35 and predecessor is : 25

I think your “BST” example and approach demonstration is partially incorrect. The node 19 cannot be left child of 18 as 19 is obviously greater than 18. This violates the basic principle of binary search tree where left child should always be less than or equal to parent and right child should be greater than parent. I would suggest you to replace 19 with 17 and the successor for 15 then becomes 17, otherwise, if right sub-tree doesn’t exist, the successor for 15 becomes 25. Please correct that. Thank you.

Very well Explained.

But minor correction as @sumeet_wilkhu:disqus pointed out.

What should be the value of successor for the element 35 (as per the tree created in main method) ? Since 35 comes last as per in-order traversal, shouldn’t its successor be null ?

Below is the code output :

In-order Successor of 35 is : 20 and predecessor is : 30

Simple solution in java for Inorder Predecessor and Successor in Binary Search Tree – https://javadiscover.blogspot.com/2018/06/inorder-predecessor-and-successor-of.html