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

Configuration and User-Defined setting in iOS

Raspberry Pi 4 Model B

How to Build Abstractions with Procedures using Scheme — ADI #1

Part II: All you need to know about Regular Expressions

Demo Application with CI/CD pipeline, deployed in Docker hub

Why every cloud computing specialist should get an AWS certification

Lambda Expressions in Java 8 (Part 1)

Replication Controller Vs Replica Set

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

Understanding Bidirectional Dijkstra’s Algorithm

All you need to know about Recursion

Understand the concept of recursion

Advent Of Code 2021 — The Treachery of Whales — Puzzle 7