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

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Avoid Fragment IllegalStateException: Can not perform this action after onSaveInstanceState

Testing APIs Protected by Azure Active Directory

5 most common code smells that you should avoid

The Importance of Coding Standards

Tracing KumuluzEE Microservices With Jaeger and Zipkin

Shifting from a car manufacturer to a software company

Database Normalization

How to Uninstall Chromium? Here’s A Simple Guide

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
Abhinay Gupta

Abhinay Gupta

More from Medium

Introduction to MATLAB

Static Analysis: A bringup, overview and additions that you will actually use

Where Is My Robot? (Part 1)

Generic FIR Filter Using Floating-Point IP in Vivado