Inorder Predecessor and Successor in BST

There is BST given with root node with key part as integer only. You need to find the inorder successor and predecessor of a given key. In case, if the either of predecessor or successor is not found return null.

Algorithm:

For Predecesor:

  1. One left and Extreme right.(If node has left subtree, then we go to the left subtree and find the rightmost node in that left subtree)
  2. Update pre while moving right. (If node has no left subtree then the predecessor is the node from the root where we took the last right to reach the given node.)

For Successor

  1. One right and Extreme left. (If node has right subtree , then go to right subtree and find the leftmost node in the right subtree , i.e. least value in right subtree.)
  2. Update suc while moving left.( If node has no right child, then we find the node from the root weher took the last left to reach given node.

Code:

class Solution {
TreeNode suc=null;
TreeNode pre=null;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
find(root,p.val);
return suc;
}
public void find(TreeNode root, int val){
if(root==null) return ;
if(root.val==val){
if(root.right!=null) suc=insuc(root);
if(root.left!=null) pre= inpre(root);
return;
}
if(root.val<val){
pre=root;
find(root.right,val);
}
else{
suc=root;
find(root.left,val);
}
}
public TreeNode insuc(TreeNode p){
TreeNode root=p.right;
while(root.left!=null){
root=root.left;
}
return root;
}
public TreeNode inpre(TreeNode p){
TreeNode root=p.left;
while(root.right!=null){
root=root.right;
}
return root;
}
}

When we are given both root and given node. We can use the below code.

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