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.
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.
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; } }
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).
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.
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;
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!
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
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; }
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; } } }
🔴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;
😌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
@@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
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; }
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
first we will traverse and reach the node for predecessor we will find the max value from the left subtree for succesor we will find the minimum value from the right subtree
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?
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?
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;
Please like and share ^ _ ^, also comment down the asked question's answer below!!
please Likeeeeeeee and subcribeeeeeee likhna tha
Thanks Striver!! :))
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.
Was looking for this comment !
Face Cam Videos Are Lit..And This setup is perfect please make all upcoming series with same setup...Its mindblowing...Kudos
This tree series is the most well curated on the entire youtube. Saying this after exploring everything.
Thank you striver bhaiya ❤️
I am a DSA beginner,is this trees series enough to crack tech giant's like Microsoft linkedin level companies?
@Raj It depends on how good your grasp is on the concepts taught
Yayyyyy... I was so scared of trees but now I started doing it.. This time I found the brute and optimal by myself.. One step at a time☺
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.
Hi Kaustubh, I had one doubt: Can we find the predecessor and the successor together in a single iteration?
@@rickk3300 yes we can, maintain two pointers and two answers and update them independently acc to their respective conditions.
@@srijall can you send the code?
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
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;
}
};
@@ashwinjain6787 hua kya fir Amazon me ?
Thanks!!
Same thoughts😅
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;
}
}
thanks bro for the solution
while(curr!=NULL){
if(curr->valval;
cur=cur->right;
}
else{
cur=cur->left;
}
}
return ans;
UNDERSTOOD.........Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
CODE: for predecessor
Node* inOrderPredecessor(Node* root, Node* p){
Node* predecessor = NULL;
while(root){
if(root->val right;
}
else
root = root->left;
}
return predecessor;
}
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).
You should remove the equal to condition when storing the predecessor, otherwise it will give wrong output
You explained it in such a intuitive and simple way. Thank you for this, man.
predecessor code :
Node * curr = root;
pre = NULL;
while(curr!=NULL){
if(curr->keyright;
}
else{
curr = curr->left;
}
}
For Predecessor if root->val >=target -> Go Left, Else Save this node as successor and then go right. Repeat until current null becomes null
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.
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.
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;
Isn't its just the Ceil of BST ? Btw the whole series is too good
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!
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
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;
}
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;
}
}
}
to find immediate smaller value of node we can store node.val which is greater then succsesor and smaller then the given input
if(p->val>root->val){
predecessor = root;
root = root->right;
}
else{
root = root->left;
}
In case of predecessor,
When we go right, we set current node as possible ans
Yeah
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..
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;
}
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);
}
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;
}
Thank you so much Striver !
🔴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;
}
Yeah
😌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
@@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
@@shineinusa yeah
Thanks for the 3rd approach.
If(p->Val>=root->Val) predecessor=root ;root=root->right;
Else root=root->left;
Return predecessor
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;
}
mind blowing striver yr _/\_ huge respect
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.
Man that's mind blowing.....everything cleared!!!
Thanks a lot Brother
Predecessor
while(root){
if(keykey){
root = root->left;
}
else{
pre = root;
root = root->right;
}
}
code for predecessor will be
while(root!=null){
if(key>root.data){
pre=root;
root=root.right;
}
else{
root=root.left;
}
}
Great content... Please do maintain this level
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
predecessor=null;
if(p.val
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
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;
}
}
}
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);
}
TreeNode predecessor=null;
TreeNode predecessor(TreeNode root,TreeNode val){
if(root==null){
return null;
}
if(root.val
Thanku bhaiya. You're the best
Predecessor
Node*pre=NULL;
while(root){
if(root->datadata){
pre=root;
root=root->right;
}
else{
root=root->left;
}
}
first we will traverse and reach the node
for predecessor we will find the max value from the left subtree
for succesor we will find the minimum value from the right subtree
Inorder successor is same as finding ceil in a string.
bro you are the best
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;
}
🌟Predecessor Code 🌟
while(root != null){
if(root.val >= x.val)
root = root.left;
else{
predecessor = root;
root = root.right;
}
}
return predecessor;
wow this is same as finding ceil or floor of bst problem,
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;
}
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;
}
@Striver bro, successor=ceil and predecesor =floor. Isn't it?
make a video on switching service to product based
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;
}
Code for both successor and predecessor:
class Solution
{
public:
Node* findPre(Node* root, int key){
Node* ans = NULL;
while(root){
if(root->key < key){
ans = root;
root = root->right;
}else{
root = root->left;
}
}
return ans;
}
Node* findSuc(Node* root, int key){
Node* ans = NULL;
while(root){
if(root->key > key){
ans = root;
root = root->left;
}else
root = root->right;
}
return ans;
}
void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
{
// Your code goes here
pre = findPre(root, key);
suc = findSuc(root, key);
}
};
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?
Isn't this same as Upper-bound/Lower-bound in BST.✅
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;
}
};
It's basically equal to finding ceil
1:50 - 3:40
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;
}
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;
}
Pls aese he tutorials lekr aeye
we love your content and we love you....🖤
yes
it is basically ceil in bst
predecessor ke liye immediate chota wala element chaiye...so we will move accordingly
Thank you Bhaiya
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?
Nope!! when key==root, root will not change and it will result in TLE.
@@devanshakruvala1354 thank you! ive been thinking about this for hours where i was wrong lol
thank you
It's ame Question as the FLOOR and CIEL value 🚀✅📄
You are doing very nice work, keep it up !
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;
}
ye pura floor or ceil Binary Search tree jesa nahi lag rha ha???
hmm same
Thanks
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};
}
Solution for Inorder Successor and Predecessor:
class Solution
{
public:
void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
{
// Your code goes here
Node* curr_pre = root;
Node* curr_suc = root;
while(curr_pre){
if(key key){
curr_pre = curr_pre->left;
} else{
pre = curr_pre;
curr_pre = curr_pre->right;
}
}
while(curr_suc){
if(key >= curr_suc->key){
curr_suc = curr_suc->right;
} else{
suc = curr_suc;
curr_suc = curr_suc->left;
}
}
}
};
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;
}
}
}
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
Thank you Brother!
Thank you sir
Loved your explanation bro!!!
//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;
}
}
}
understood!
what is the difference between inorder successor and ceil of BST.
So it is basically the ceil and floor of a number in a bst
understood
Node* inorderPre(Node* root,Node* p){
Node*predecessor=NULL;
while(root){
if(p->datadata){
root=root->left;
}else{
predecessor=root;
root=root->rigth;
}
}
return predecessor;
}
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;
Isn't it a modified Ceil/ Floor problem?
Thanks a lot again Striver
understood.
public static BinaryTreeNode inOrderPredecessor(BinaryTreeNode root,
BinaryTreeNode p){
BinaryTreeNode predecessor = null;
while(root!=null) {
if(root.data >= p.data) root = root.left;
else {
predecessor = root;
root = root.right;
}
}
return predecessor;
}
TreeNode *predecessor=NULL;
while(root!= NULL)
{
if(root->val val)
{root=root->right;
predecessor=root; }
else
{ root=root->left;}
}
return predecessor;