L49. Inorder Successor/Predecessor in BST | 3 Methods

Entire DSA Course: takeuforward.o...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/take...
#treeSeries #striver #placements

[@takeUforward]

Please like and share ^ _ ^, also comment down the asked question's answer below!!

[@shashankbajpai5659]

please Likeeeeeeee and subcribeeeeeee likhna tha

[@priyanshkumar_iitd]

Thanks Striver!! :))

[@nitinkumarsingh7959]

In 3rd method the basic idea is same as finding ceil of a node in bst. The only change here is that the ceil value must be just greater than the node and rest everything is same. And the predessor one is same as findind floor value which is not equal to and just less than.

[@ayushbhandarkar8394]

Was looking for this comment !

[@atharvakulkarni2024]

Face Cam Videos Are Lit..And This setup is perfect please make all upcoming series with same setup...Its mindblowing...Kudos

[@sparshsharma3150]

This tree series is the most well curated on the entire youtube. Saying this after exploring everything.
Thank you striver bhaiya ❤️

[@tech_wizard9315]

I am a DSA beginner,is this trees series enough to crack tech giant's like Microsoft linkedin level companies?

[@sparshsharma3150]

@Raj It depends on how good your grasp is on the concepts taught

[@tejasmishra7130]

Inorder predecessor in BST of given Node
class Solution {
public:
TreeNode * inorderPredecessor(TreeNode * root, TreeNode * p) {
TreeNode* predecessor = NULL;
while(root!=NULL){
if(root->val >= p->val){
root = root->left;
}
else{
predecessor = root;
root = root->right;
}
}
return predecessor;
}
};

[@saurabhjejurkar5065]

@@ashwinjain6787 hua kya fir Amazon me ?

[@priyanshkumar_iitd]

Thanks!!

[@lovegoyner7450]

Same thoughts😅

[@kaustubhwaghavkar9079]

Intuition for predecessor:
-Basically if root.val >= p.val then just go left because predecessor should ideally be on the left so we do not even have a potential predecessor to set at this point because it has to be smaller than the p's val.
-On the other hand, if root.val < p.val, then we can have a potential predecessor(may or may not be immediate) so we store root.val into predecessor and move right to find a larger value than current predecessor but less than p's val (basically closer value to p but should be less than p of course).
-In the end when we reach null, we will have predecessor which we will return.
Python Code:
def inorderPredecessor(self, root, p):
predecessor = None
while root:
if root.val >= p.val:
root = root.left
else:
predecessor = root
root = root.right
return predecessor
Complexity Analysis(will be same as successor)
TC: O(H) because we traverse the height of the tree (left, right, left, right) and skip the other subtree entirely so we are saving time there too.
SC: O(1) because we are again just changing root pointer all the time and not using recursion to have auxiliary stack space too.

[@rickk3300]

Hi Kaustubh, I had one doubt: Can we find the predecessor and the successor together in a single iteration?

[@srijall]

​@@rickk3300 yes we can, maintain two pointers and two answers and update them independently acc to their respective conditions.

[@rickk3300]

@@srijall can you send the code?

[@amanshah1650]

Another approach :- O(H) time complexity and O(1) space complexity
To find suc and pre for key.(covered both the cases key in tree/not in tree)
void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
{
pre=NULL;suc=NULL;
while(root){
if(root->key==key){
if(root->left){
auto rightmost=root->left;
while(rightmost->right)rightmost=rightmost->right;
pre=rightmost;
}
if(root->right){
auto leftmost=root->right;
while(leftmost->left)leftmost=leftmost->left;
suc=leftmost;
}
break;
}
else if(root->key>key){
suc=root;
root=root->left;
}
else {
pre=root;
root=root->right;
}
}
}

[@kotipallimadhumeher71]

For predecessor,which ever nodes is smaller than val,that is one of possible predecessor
Then we move to right side to check whether there are any nodes greater than current predecessor and smaller than val
If node is greater than val,then we'll move to the left.Because we know,On the right side of node which has bigger value also have bigger values so there is no chance there will be a predecessor.
/*code*/
class Solution{
public TreeNode inorderPredecesspr(TreeNode root,TreeNode p){
TreeNode predecesor=null;
while(root!=null){
if(root.val>=p){
root=root.left;
}
else{
predecesor=root;
root=root.right;
}
}
return predecesor;
}
}

[@vishalgupta7522]

thanks bro for the solution

[@rishabhkumar8115]

CODE: for predecessor
Node* inOrderPredecessor(Node* root, Node* p){
Node* predecessor = NULL;
while(root){
if(root->val right;
}
else
root = root->left;
}
return predecessor;
}

[@elijahmikaelson740]

sir i think there is a problem with this code when i am applying this on the tree with which the striver had explained the optimal solution of successor then it's giving wrong predecessor please check your code once (i tried to find the predecessor of 4).

[@harishsn4866]

You explained it in such a intuitive and simple way. Thank you for this, man.

[@World-Of-Mr-Motivater]

to find the inorder predecessor
we can do the following:
i) go to node left and store it in predecessor variable
ii)then go to it's right and store it
so inshort:
move to the node left
if node has right move to it
if node is empty then the one at the rightmost is our answer;

[@shantanuahuja5256]

I solved successor many times but didn't come up with all the cases on my own and by watching our video today everything is clear to me .Maza aagaya

[@ravisingh-el8np]

predecessor code :
Node * curr = root;
pre = NULL;
while(curr!=NULL){
if(curr->keyright;
}
else{
curr = curr->left;
}
}

[@user-yp7lm9em2n]

while(curr!=NULL){
if(curr->valval;
cur=cur->right;
}
else{
cur=cur->left;
}
}
return ans;

[@rohanmalik1772]

For Predecessor if root->val >=target -> Go Left, Else Save this node as successor and then go right. Repeat until current null becomes null

[@sujan_kumar_mitra]

In case of predecessor,
When we go right, we set current node as possible ans

[@takeUforward]

Yeah

[@stith_pragya]

UNDERSTOOD.........Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@abhaypratapsingh1457]

if(p->val>root->val){
predecessor = root;
root = root->right;
}
else{
root = root->left;
}

[@isheep9025]

self note alternate appraoch with 0(H+H) TC and 0(1) sc- find the note using binary seach tree algo, keeping track of previous node visited,if we find a leaf node return last node which we kept a track of ,else find leftmost node of the right subtree from the node we found out,if we have encountered the last node return null

[@kushagrasahay]

this intuition for finding inorder predecessor and successor is similar to finding floor and ceil of node in BST. simple binary search applied to a tree. Anyways great explanation, striver bhaiya. really inspired.

[@Avinashkumar-yq2zr]

TreeNode * inorderPredecessor(TreeNode * root, TreeNode * p)
{
TreeNode*ans=NULL;
while(root)
{
if(root->val < p->val)
{
ans=root;
root=root->right;
}
else
root=root->left;
}
return ans;
}

[@misterr_stupied3747]

to find immediate smaller value of node we can store node.val which is greater then succsesor and smaller then the given input

[@anshulsharma3137]

Isn't its just the Ceil of BST ? Btw the whole series is too good

[@thinkingmad1685]

So my answer of predecessor will be similar to finding floor value approach
TreeNode * predecessor(TreeNode* root, TreeNode * p) {
TreeNode * pred =nullptr;
If(!root) return pred;
While(root! =nullptr) {
If(root->valval) {
pred=root;
root=root->right;
}
else
root=root->left;
}
}
return pred;
}

[@gabrieldias6430]

perfect explanation! I guess the only thing that doesn't make this video better is that you implemented iteractively, but, except from that, really good video! Thanks for sharing your knownledge!

[@bhumithakur9967]

In case of predecessor , we'll store the value less than given val for that..so when we move right we store root in curr val..

[@akashpal7748]

Hey striver bhaiya, here is the homework
public static Node findPre(Node root,int key,int node){
if(root == null){
return new Node(node);
}
if(key>root.data){
return findPre(root.right,key,root.data);
}
return findPre(root.left,key,node);
}

[@jayantmishra6897]

he is like a dronaachrya for us and we are eklavya for him. he don't know about us but we are the student of him.

[@rishabhbatra3022]

🔴Code for Predecessor, Just opposite of successor, so just change the if-else conditions according to question demand and It will work fine🔴
TreeNode* inorderPredecessor(TreeNode* root, TreeNode* p) {
TreeNode* predecessor = NULL;

while (root != NULL) {

if (p->val < root->val) {
root = root->left;
} else {
predecessor = root;
root = root->right;
}
}

return predecessor;
}

[@takeUforward]

Yeah

[@shineinusa]

😌This code fails to find the predecessor, you are travelling left only when the target value is less than root value, but you are not travelling left when both target and root values are equal!
Correction would be
TreeNode predecessor = null;
while (root != null) {
if (p.val

[@neilchaudhary007]

@@takeUforward the above solution will not work, try DRY of this solution the solution that will work is this one
TreeNode* successor(TreeNode* root, TreeNode* k){
TreeNode* pre = NULL;
while(root != NULL){
if(k -> val > root -> val ){
pre = root;
root = root -> right;
}
else
root = root -> left;
}
return pre;
}
and the error in above solution is instead of

[@adityaajay29]

@@shineinusa yeah

[@pururajsinghrajawat5348]

It's the same concept as ceil and floor of a BST with a little difference that ceil and floor can't be equal to the given key.

[@jarangvinayak.5435]

TreeNode predecessor=null;
TreeNode predecessor(TreeNode root,TreeNode val){
if(root==null){
return null;
}
if(root.val

[@PriyanshJwalantYadav]

Man that's mind blowing.....everything cleared!!!
Thanks a lot Brother

[@sidhantjha4566]

Predecessor
while(root){
if(keykey){
root = root->left;
}
else{
pre = root;
root = root->right;
}
}

[@Mysterious_debris_1111]

Great content... Please do maintain this level

[@akashsahu2571]

yes

[@ravipatiramya4185]

If(p->Val>=root->Val) predecessor=root ;root=root->right;
Else root=root->left;
Return predecessor

[@neilchaudhary007]

This solution will not work because in this what will happen when we check p-> val >= root->val it will update the predecessor to the given root and not the value just before if so that you need to right the same solution and now instead of >= use only > and you will be good to go otherwise you can DRY your code and then you will see and here is the updated code
TreeNode* successor(TreeNode* root, TreeNode* k){
TreeNode* pre = NULL;
while(root != NULL){
if(k -> val > root -> val ){
pre = root;
root = root -> right;
}
else
root = root -> left;
}
return pre;
}

[@eklavyaprasad5009]

predecessor=null;
if(p.val

[@shivanjali3909]

Method 2 implemented by Recursively
void presuc(TreeNode* root, int& pre, int& suc, int key)
{
if (root == NULL)
return;
presuc(root->left, pre, suc, key);
if (root->data < key)
pre = root->data;
if (root->data > key && suc == -1)
suc = root->data;
presuc(root->right, pre, suc, key);
}

[@vaalarivan_p]

1:50 - 3:40

[@rishabhgupta9846]

Code for both Successor/Predecessor
void findPreSuc(Node *root, Node *&pre, Node *&suc, int key)
{
pre = NULL;
suc = NULL;
Node *node = root;
while (node)
{
if (node->key right;
}
else
{
suc = node;
node = node->left;
}
}
node = root;
while (node)
{
if (node->key >= key)
{
node = node->left;
}
else
{
pre = node;
node = node->right;
}
}
}

[@vaibhavsharma4553]

Node* inorderpredesessor(Node* root, int val){
Node* pred = root;
while(root!=NULL){
if(val >= root->data){
pred = root;
root = root->right;
}
else{

root = root->left;
}
}
return pred;
}

[@aaryanverma2000]

Thanku bhaiya. You're the best

[@MadhurGupta-f7p]

bro you are the best

[@aswinikumarsahoo6459]

Inorder predecessor of BST in Java (node to be returned) :
Node inorderPredecessor(Node root, Node target)
{
Node predecessor=null;
while(root!=null)
{
if(target.data > root.data)
{
predecessor=root;
root=root.right;
}
else if(target.data

[@avinashbhatia3303]

Inorder successor is same as finding ceil in a string.

[@ashugupta6248]

ye pura floor or ceil Binary Search tree jesa nahi lag rha ha???

[@ettireddyspandana]

Node* Pred(Node* root, Node* p)
{
Node* predi=NULL;
while(root)
{
if(root->val >= p->val) root=root->left;
else
{
predi=root;
root=root->right;
}
return predi;
}

[@InfinteMotivation]

mind blowing striver yr _/\_ huge respect

[@mrrishiraj88]

Thanks

[@anirbanbera5630]

Predecessor
Node*pre=NULL;
while(root){
if(root->datadata){
pre=root;
root=root->right;
}
else{
root=root->left;
}
}

[@theautumnleaves343]

void predecessor(Node* root,Node*& pre,int key) {
while(root) {
if(root->keyright;
}else root=root->left;
}
}
void successor(Node* root, Node*& suc, int key) {
while(root) {
if(key>=root->key) root=root->right;
else {
suc=root;
root=root->left;
}
}
}

[@deepaktiwari7059]

Python code to find both predecessor & Successor :
def findPreSuc(root, pre, suc, key):
temp = root
while root and root.key != key:
if root.key < key:
pre[0] = root
root = root.right
else:
suc[0] = root
root = root.left

# Predecessor is going to be right most node on the left subtree if left node exist
if root.left:
prev = root.left
while prev.right:
prev = prev.right
pre[0] = prev
# successor is going to be left most node on the right subtree if right node exist
if root.right:
prev = root.right
while prev.left:
prev = prev.left
suc[0] = prev

[@AnimishTripathy]

HOMEWORK DONE STRIVER BHAIYA 👍
Node* findPredecessor(Node* root, Node* p) {
if(!root)
{
return NULL;
}
Node* predecessor=NULL;
Node* curr=root;
while(curr)
{
if(curr->data < p->data)
{
predecessor=curr;
curr=curr->right;
}
else
{
curr=curr->left;
}
}
return predecessor;
}

[@lavanyaprakashjampana933]

we love your content and we love you....🖤

[@akhilkishore7361]

make a video on switching service to product based

[@rakshitpandey7517]

Simplest Solution- (Before seeing the Soln in the video)...:)
Node * inOrderSuccessor(Node *root, Node *x)
{
Node *curr=NULL;
while(root)
{
if(root->data>x->data)
{
curr=root;
root=root->left;
}
else
{
root=root->right;
}
}
return curr;
}

[@shubamgoswami]

it is basically ceil in bst

[@gunjanbiswas925]

predecessor ke liye immediate chota wala element chaiye...so we will move accordingly

[@UECAshutoshKumar]

Thank you sir

[@thefizzshow]

Loved your explanation bro!!!

[@amitsinghrana6619]

Isn't this same as Upper-bound/Lower-bound in BST.✅

[@horccruxxxop4184]

Pls aese he tutorials lekr aeye

[@rashmi_gaur]

Thank you Brother!

[@Aditya-mx8rp]

thank you

[@shinewanna3959]

Presuccessor Answer in Dart
presuccessor(TreeNode? root, int target) {
int? presucessor;
f(TreeNode? root) {
if (root == null) {
return null;
}
if (root.val < target) {
presucessor = root.val;
f(root.right);
} else if (root.val >= target) {
f(root.left);
}
}
f(root);
return presucessor;
}

[@vikrambabariya5166]

You are doing very nice work, keep it up !

[@adityagarg9806]

It's basically equal to finding ceil

[@rosonerri-faithful]

@Striver bro, successor=ceil and predecesor =floor. Isn't it?

[@ideepakpandey]

predcessor code:-
TreeNode* predcessor(TreeNode* root,TreeNode* p){
TreeNode* pred=NULL;
while (root!=NULL)
{
if(p->data > root->data){
pred=root;
root=root->right;
}
else{
root=root->left;
}
}
return pred;
}

[@shadabfaisal801]

public static TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
TreeNode predecessor=null;

while(root!=null) {
if(p.val>root.val) {
predecessor=root;
root=root.right;
}
else {
root=root.left;
}
}
return predecessor;
}

[@mugambo5505]

predecessor
int sucess(node *root, int key)
{
static int ans = INT_MIN;
if (root == NULL)
{
return -1;
}
if (root->data >= key)
{
sucess(root->left, key);
}
else
{
ans = max(ans, root->data);
sucess(root->right, key);
}
return ans;
}

[@Shivi32590]

understood

[@Codebreaker0702]

[@satyapraneethkatta1652]

Thanks a lot again Striver

[@harshitjaiswal9439]

understood.

[@neelshah6695]

🌟Predecessor Code 🌟
while(root != null){
if(root.val >= x.val)
root = root.left;
else{
predecessor = root;
root = root.right;
}
}
return predecessor;

[@akarshjain3028]

same concept as floor and ceil question only difference in this we avoid same value.

[@iriyaagrawal]

code for predecessor will be
while(root!=null){
if(key>root.data){
pre=root;
root=root.right;
}
else{
root=root.left;
}
}

[@sawankundu1898]

//Predecessor
public static void predecessor(Node root, Res p, int key){
while(root != null){
if(root.data >= key){
root = root.left;
}else{
p.pre = root;
root = root.right;
}
}
}

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@divy04]

Predecessor code
Node* temp=root;
Node* par=NULL;
int k=x->data;
while(temp){
if(temp->dataright;}
else if(temp->data>k){temp=temp->left;}
else temp=temp->left;
}
if(par==NULL||par->data>=k)return NULL;
return par;

[@debugagrawal]

It's ame Question as the FLOOR and CIEL value 🚀✅📄

[@abhishekanand9430]

Node *findpre(Node *root,int key,Node *&pre)
{
if(root==NULL)
return root;
while(root!=NULL)
{
if(root->key < key)
{
pre=root;
root=root->right;
}
else
{
root=root->left;
}
} }

[@atharvacharde5628]

Sir these approach is no doubt good but consider a case in which only key given for which successor has to be find and not root given then how to find out it?

[@KanakKhandelwal-oh4fy]

Node* inorderPredecessor(Node* root, Node* p){
Node* predecessor = NULL;
while(root!=NULL){
if(p->datadata){
root = root->left;
}else{
predecessor = root;
root = root->right;
}
}
return predecessor;
}

[@ruchitasharma2842]

For Both the Predecessor and Successor:
ArrayList list = new ArrayList();
int successor = -1;
int predecessor =-1;
while(root!=null){
if(key>root.val){
predecessor = root.val;
root= root.right;
}
if(key< root.val){
successor = root.val;
root= root.left;
}
}
list.add(predecessor);
list.add(successor);
return list;
}
Is it correct?

[@devanshakruvala1354]

Nope!! when key==root, root will not change and it will result in TLE.

[@shivansh709]

@@devanshakruvala1354 thank you! ive been thinking about this for hours where i was wrong lol

[@utkarshsharma6650]

understooood. thanks :)

[@ghj7275]

class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode predecessor = null;
while(root != null) {
if(root.val > p.val) {
root = root.left;
} else if(root.val == p.val) {
root = root.left;
} else {
if(predecessor == null || predecessor.val > root.val)
predecessor = root;
root = root.right;
}
}
return predecessor;
}
}
@takeUforward code for finding predecessor

This is the same as finding the floor/ceil of a value in a BST

[@average_aspirant]

what is the difference between inorder successor and ceil of BST.

[@mandeepsinghsoorma3080]

This is the solution to the codeStudio problem "Finding the predecessor and successor in a BST"
pair predecessorSuccessor(BinaryTreeNode* root, int key) {
auto p=-1, s=-1;

// finding predecessor
auto t=root;
while(t) {
if(t->data < key) p=t->data, t=t->right;
else t=t->left;
}

// finding successor
t=root;
while(t) {
if(t->data > key) s=t->data, t=t->left;
else t=t->right;
}
return {p,s};
}

[@Manishgupta200]

Logic is same from Q. floor and ceil in BST
private:
Node* successor(Node* root, Node* suc, int key){
if(root == NULL) return NULL;
suc = NULL;
while(root != NULL){
if(root->key > key){
suc = root;
root = root->left;
}
else{
root = root->right;
}
}
return suc;
}
Node* predecessor(Node* root, Node* pre, int key){
if(root == NULL) return NULL;
pre = NULL;
while(root != NULL){
if(root->key < key){
pre = root;
root = root->right;
}
else{
root = root->left;
}
}
return pre;
}
public:
void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
{
// Your code goes here
// TC -> O(H)
// SC -> O(1), no any extra space use apart from recursive stack space
suc = successor(root, suc, key);
pre = predecessor(root, suc, key);
}

[@roopeshn3301]

Understood

[@tushar7305]

Sir, i want to learn dsa from where can i learn ????i have leanrt basic of c++

[@krishnarajs929]

Hiii bro , You can start from linkedlist before that you need to know Recursion , it will be helpful

[@amanbhadani8840]

CODE FOR INORDER PREDECESSOR ----
class Solution {
public:
TreeNode* inorderPredecessor(TreeNode* root, TreeNode* p) {
TreeNode* Predeccessor = NULL;

while (root != NULL) {

if (p->val > root->val) {
Predeccessor = root;
root = root->right;
} else {
root = root->left;
}
}

return Predeccessor;
}
};

[@sarthaksharma6973]

So it is basically the ceil and floor of a number in a bst

[@chiragbansod8252]

inorder perdecessor code java -> public TreeNode predecessor(TreeNode root, TreeNode p) {
TreeNode ans = new TreeNode(Integer.MIN_VALUE);
TreeNode temp = root ;
while(temp != null){
if(temp.data temp.data){
if(ans.data < temp.data) ans = temp;
}
temp = temp.right;
}else{
temp = temp.left;
}
}
if(ans.data == Integer.MIN_VALUE) return null;
return ans;
}

[@palakjain2505]

the best

[@jaiminsolanki5478]

Understood!

[@nishanth1828]

Isn't it a modified Ceil/ Floor problem?