Inorder Predecessor and Successor in BST

  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.)
  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.
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;
}
}
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;
}
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store