Inorder Successor in a binary search tree

See complete series on data structures here:
• Data structures
In this lesson, we have discussed efficient algorithm to find Inorder successor of a Node in binary search tree.
See source code here:
gist.github.com/mycodeschool/...
See video on Inorder Traversal here:
• Binary tree traversal:...
For practice problems and more, visit: www.mycodeschool.com
Like us on Facebook: / mycodeschool
Follow us on twitter: / mycodeschool

[@llarn.i5103]

It’s been 10 YEARS since this playlist and people are still watching it, I don’t usually comment but Really Thank you for this masterpiece

[@DhirendraSingh03]

This entire playlist is a treasure. Downloaded all the videos and created multiple copies in my PC, my external hard drive and google drive. Cannot risk it losing in case of apocalypse. And whoever you are, a big thank you. You are a GOAT.

[@robinsoni4778]

No, he is not a GOAT, He is a human

[@Slim7073]

@@robinsoni4778 He capitalized GOAT. It stand for Greatest Of All Time.

[@ApoorvaRajBhadani]

kuch zyada ho gya...............tareef karne ka tarika tera mujhe kuch khas acha nhi laga 😂

[@konstantinrebrov675]

@@Slim7073 That is ambiguous abbreviation. There could be 100 things it stand for. And "goat" sounds like a bad word.

[@danilo2735]

@@konstantinrebrov675 it's a word used in many places, for example messi is the football goat, jordan the basket goat etc...

[@user-zd6rj9vt6c]

finally i find someone who explain all things with details thank you so much

[@shelbygt5004]

mycodeschool Your tutorials are BRILLIANT! Please do continue the series as soon as possible. Would like to see more on Trees, Graphs, Maps, Hash-tables etc.

[@Leon-hg1ph]

Yooo, this whole concept of BST is freaking amazing, almost magical. Thanks a lot for sharing this mate!

[@narayankaadda772]

Hi Sir, I have followed all your BST tutorials. It was very great and clear explanation. Initially I was afraid of learning BST. Now I can say I have learned BST confidently from your explanation. Thank you very much your contribution to helping programmers.

[@darshpreetsingh2010]

All videos are great,most important thing is that they are all very interactive and you have worked very hard in making them and teaching us. Thankyou

[@deeepbagadiya]

After 2 Years...THis videos Helped the same.....i am sure till many years this videos will keep helping Students

[@random-0]

yes it's still rocking he left us a treasure

[@manishpandey3803]

yes today's date is 30/05/2020

[@sudhanshu9831]

2021 and still the easiest and understandable explanation of ds on yt

[@AmanKUMAR-vq1ls]

I am here on 20 july 2021

[@jatinvashisht4293]

😂 This aged very well

[@prudvi01]

I'm watching this series after my engineering, these data structures make much more sense now thank you so much

[@darshanbhat9457]

I am a beginner in DS. These videos helped me a lot to understand quickly. Thanks a lot. Please don't stop uploading. Keep going.

[@abhilashnair6660]

He stopped lol

[@monikajha3500]

He is no more in this cruel world :(

[@saeem01670]

@@monikajha3500 what do you mean by that? :|

[@noobcoder5988]

@@monikajha3500 No, he is alive.

[@random-0]

@@noobcoder5988 sorry but sadly he is dead search for it

[@harinijeyaraman8789]

Kudos for your efforts in making concepts seem this easy ! Love your channel. Really helpful !!

[@1gouravgg]

finally completed the whole DS series :)

[@kausshin5404]

And got placed at google

[@prajwalchoudhary4824]

@@kausshin5404 lol

[@HARIHaran-ks7wp]

@@kausshin5404 wait, really??

[@manishkumargupta8677]

Congratulations

[@Drogon-Gaming]

this play list is absolute bonus for every programmer who wants to get good at data structure , Many thanks to CS DOJO for suggesting this !!!!!

[@findoc9282]

Most enjoyable experience i ever had of online learning, so much love and respect.

[@shubhammohapatra7766]

Really, great stuff man. You have helped a lot of people. You should be really proud of yourself.

[@codingandmathvideos]

Impressive. Thanks a million times. You are simply the best.

[@sarveshp1727]

This is THE PERFECT explanation of this concept.

[@Marko-vb2mi]

Dude, you just I locked my brain on this. Thank you so much!

[@parthkhanna8542]

Man...U are an inspiration for me.. You are just great.. No words can express your work.. Thanx for helping

[@scotfsh5014]

I'm in tear watching your video sir, the way you spreading knowledge is on god tier, I coundn't been more satisfied with my life without learning from you.Much Love!

[@__hannibaal__]

Yeah i stop C++ 25 years ago, and i busy with mathematic, until last year, and per chance i step on these videos on C++ and data structure, and he gave me another breath and i start learn what i lost before, very effective __my back ground mathematic help me__ and now i just i have 80% of C++, and data structure 60%, and this second year is planed to make all data structure __special a complex tree with modern C++__ from scratch and both .

[@RahulSharma-hp6hv]

Keep it up dude! you deserves appericiation

[@AnonymousCoder7]

I'm gonna hit Like 👍🏻to every video of this channel coz It Deserves !!

[@saiudaybhaskarmudivarty7502]

Thanks for the video series. They've been really helpful for me these days. Can you please do a series on Balanced Binary trees and Tries as well. Thanks in advance.

[@prashantbacchewar8194]

Your videos are "the" best Any plan to cover self balancing trees like Red Black or AVL trees

[@sumitsaini1601]

getSucessor in case II is really insightful and elegant. That sums up this video.

[@iamparitosh]

Completed all the 13 Videos on BST I feel like a BST Master and able to complete most Leetcode problems on BST:)

[@sajalagrawal1430]

Bro u are the best . cleared all doubts

[@butlikereally]

this is really really helpful. THANK YOU

[@yuiooiuyyuiooiuyyuio]

Hi I'm Kapil, These codes for successor and predecessor seem to work fine. They keep on storing the pointer to nodes whose value is greater than (or less than) the given integer in the path of search for the integer and the latest updated value is our answer. And also when it finds the integer, it doesn't stop, it goes on to find the next greater value (or smaller) by traversing further down the tree. It's a tiny code :) TreeNode* getSuccessor(TreeNode* A, int B) { TreeNode *P=NULL; while(A!=NULL) { if(A->valright; } else if(A->val>B) { P=A; A=A->left; } } return P; TreeNode* getPredecessor(TreeNode* A, int B) { TreeNode *P=NULL; while(A!=NULL) { if(A->valright; } else if(A->val>=B) { A=A->left; } } return P;

[@panavsethi3014]

It actually works fine, the time complexity is also O(h). I wonder why he used such a complex algorithm.

[@shradheytripathi7564]

Sir,I am a big fan of this channel.Please upload videos of some more topics of Data Structures.

[@williamwambua7710]

Thank you very much...step by step I like that!! Bravoooo!!! wish you could make more videos on computer science

[@techswissknife2858]

Hey, great video thanks a lot. I was wondering a few things about the code you wrote: Is it better in C++ to use nullptr instead of the C macro NULL ? Is temp a good variable name? Coud we call the variable "successor" to make clear we're returning the successor? Is this: while(temp->left != NULL_ temp=temp->left; equivalent to: while (temp = temp->left) { ; //do nothing } Which one is a better c++ idiom?

[@sarveshsant1337]

In Getsuccessor function instead of: "if(current->data < ancestor->data)" we must use :if(current->data data)" To ensure the data less or equal will be found in left subtree. Thanks for sharing your knowledge.

[@hughlee5648]

i think you won't have to check equal condition since in BST, duplicate is not allowed anyways.

[@VC-kj9yx]

Thank u so much i finally understood this successor thing

[@chayakumarsedutainment4799]

You haven't handled the case when current node is leaf node. Yet, still it is an excellent tutorial for DS and I will recommend this to other. I have learnt a lot from you. Thank you so much..

[@ganapatibiswas5858]

It will fall into the current -> right==null case

[@stage666]

your videos are the best i can find. I love u

[@monicaslv323]

+yoshinosakura Noooo. I love them more. :p

[@prabaljainn]

love me too

[@zaneran5933]

Good analysis!

[@arunkumargupta1947]

i really enjoyed while watching each and every videos. can you add some videos of threaded binary tree if possible.............

[@Roover_sa]

brother make an updated playlist of ds-algo with same explanation . i have not words to express who you are

[@namans9803]

sir , in this we don't have condition to check if the element is largest ,then there will be no successor.Can we use a find max function to check if it is the largest element ? will it affect the time complexity ??

[@dr_920]

If it is the max element in the BST, it should return null. The video doesn't take this corner case into consideration. Anyway, another really fantastic video. I learned a lot from the whole series. Thank you.

[@RP-th8in]

what about 11, what case does it fall into

[@shubhamgoyal3100]

if the right subtree is present, the successor will be the node with the minimum value in right subtree else successor will be the node where we took the last left turn while searching for the current node.

[@niyas09]

very good explanation

[@olly779]

you have a very good English!

[@nitinjaiman]

can you make videos on red black trees, greedy algo, kruskal algo and other topics that are in cormen. i went through mit videos i must say you are better than those fancy professors

[@PROcrastiDRIVESVofficial]

Excellent! Thank you.

[@siddalingammakasbag5360]

thank you sir it very much cleared way

[@ScrappyVids]

@mycodeschool, thanks for the video!, but I believe you should create the video for the predeccessor, in the end people use this videos to learn, but also as reference... dont treat us bad :(

[@shaiksoofi3741]

Hats off.Its a treasure

[@sumitsaini1601]

Woh, you did a problem on iterative inorder traversal without stack!

[@jonsnow9246]

This isn't inorder traversal

[@kritikasinghal8015]

sir,please made video on combinations of sum

[@gobibs1]

pls talk about n-ary tree

[@kautukraj]

Very helpful!

[@roshantopno1253]

great work

[@ankitsingh8087]

Can you add one more lecture on avl tree before graph.. That is the thing which is missing in your lectures

[@rahil_rehan]

theNewBoston of Indian software youtubers!

[@SumitKumar-fn3gj]

Thank You Sir

[@usama57926]

thank u bro

[@wisepalaz]

what is the successor of 27 or 25 in this case?

[@---xk4iw]

why there are ont avl tree?

[@listlist8982]

Hi! Your code had an error when I compiled it. The error is in the last line return successor; and says that successor undeclared (first use in this function). I delcared struct node * successor = NULL; at the top but then it doesn't return anything cause its Value is NULL and the value never changes inside the else statement! How can I fix it?

[@sheardz6380]

Thanks

[@worldfromhome4033]

Thank you is all I can say!

[@heenagirdher6443]

Thanks sir.....

[@namangupta2587]

Plss make more videos on graphs

[@wangchi562]

bro, please come back!

[@cherrynaresh3111]

while(ancestor != current) will not work to find inorder successor of a element in right subtree. So if we change it to while(ancestor != null) i think it will work.

[@rohankademani6406]

Finally completed !!!

[@looploop6612]

how does it come back from 6 to 8?

[@DevGamerShripadAgashe]

AVL tree please

[@effy1219]

excellent

[@gabrielpereiramendes3463]

Very Good!

[@bpunsky]

I noticed it's been a while since you uploaded any data structure videos. Will there be more, or is this the end of the line? Also, if you do continue the series, it would be cool to see a hashmap/hashtable implementation.

[@mycodeschool]

***** No this is not an end. My co-founder who was an amazing friend passed away in an accident and I have not been able to focus much after that. Its been a hit. I am trying to reset things and keep this project going. Expect some videos in this data structures series in August. Video creation is slow and creative process. But 4-5 videos in a month is still something that I can do. -Animesh Nayan Co-founder, MyCodeSchool

[@bpunsky]

mycodeschool Wow, sorry to hear that. Not much I can really say other than that I feel for you and hope you come out the other side alright. It really makes the lack of videos seem insignificant by comparison, but I'm glad to hear that you are going to continue with your channel - it's very informative and I imagine helpful to a lot of people. Good luck and again, I'm very sorry to hear about your friend.

[@1gouravgg]

***** in addition, he was the No.1 coder of India!!

[@wingzero1912]

You've been very helpful Animesh for a lot of people out there.

[@santwanadutta4488]

I guess that successor=ancestor, you have to define outside the if block. Am I correct please reply someone.

[@arjunpassi9945]

Can't you traverse (right root and then left) and check if the next node you are going to traverse is the one you are looking the successor for?

[@rishigoley3521]

Complexity would be O(n) for your approach.

[@gauravchauhan873]

what about AVL and B+ trees

[@manojpatial2404]

share one tut on threaded binary tree if possible ;)

[@TonyDaExpert]

did he cover AVL trees?

[@albertpatterson8164]

I like this.

[@kashishmiglani6576]

great

[@frozentaco143]

Great video. But it would have been much clearer if in case2 code, ancestor was named as temp and successor was named as ancestor.

[@amateurbeginner7538]

u are bossssssss

[@vasantprabhu]

in the else part inside while loop ,we need a "sucessor=ancestor" there too i think (right subtree part)

[@vasantprabhu]

update : - i am wrong . the code is correct. explanation is at 16:55 . not all nodes will have a successor. there is no successor the right most node.

[@HeWhoShalNotBeNamed_]

dude, a single optimization to propose, why not maintain the successor while you find the node? if right subtree doesnt exists,we simply return that value.. this way we sorta save the second traversal in else conditon. ideally it would be o(h) + o(h) but when we maintain it, it would turn out to be only o(h) single go. Find could be modified as :- > Node* Find(Node* root,Node* succ, int data){ Node* ancestor = root; while(ancestor->data != data){ if(data < ancestor->data){ succ = ancestor; ancestor = ancestor->left; } else{ ancestor=ancestor->right; } } return ancestor; } so , as soon as else is triggered, we directly return the succ node that we maitained during FInd().

[@rimpinag6346]

Plz tell me sir whats ur name?? Really amazing video

[@manfredoweber3562]

i dont know if its good practice, but it a different faster implementation in trade off for higher memory requierements Node* successor(Node * root, int data, Node * ancestor=NULL){ //if found, return either right sub or ancestor if(root->data==data){ if(root->right!=NULL)return root->right; else return ancestor; } // search for Node, if call for left sub, give self as arg if (datadata)return successor(root->left, data, root); else return successor(root->right, data, ancestor); }

[@RaviRanjan_ssj4]

***** you said that you will be making more lessons on problems on Binary Trees and Binary trees in this video. Why did you stop ?

[@desihaxor5690]

his best friend died in a car accident

[@hafizulislamhimel7742]

Sir is this only for time complexity ??? because you already posted tree traversal video.....

[@bharaniakella7734]

Java code for inorder predecessor-> public Node inOrderPredecessor(Node root,int key){ Node current=search(root,key); if(current==null)return null; if(current.left!=null){ return max(current.left); }else{ Node ancestor=root; Node predecessor=null; while(ancestor!=current){ if(key>ancestor.data){ predecessor=ancestor; ancestor=ancestor.right; }else if(key

[@rhythmpatel5665]

Needed this. Thanks :)

[@meghasyam427]

things r getting real tough...

[@amateurbeginner7538]

Inorder presecessor code in c : enjoy guys :) struct node* Getpresecessor( struct Node* root , int data ) { // Search the Node - O(h) struct node* current = Find(root,data); if(current == NULL) return NULL; if(current->left != NULL) { //Case 1: Node has right subtree return maxValueNode(current->left); // O(h) } else { //Case 2: No right subtree - O(h) struct node* presecessor = NULL; struct node* ancestor = root; while( ancestor != current ) { if( current -> key > ancestor -> key ) { presecessor = ancestor; // so far this is the deepest node for which current node is in left ancestor = ancestor->right; } else ancestor = ancestor->left; } return presecessor; } } struct node * maxValueNode(struct node* node) { struct node* current = node; /* loop down to find the leftmost leaf */ while (current->right != NULL) current = current->right; return current; }

[@AbhishekKumar-yv6ih]

// so far this is the deepest node for which current node is in left. correction: left should be right.

[@ArjunSoota]

GOAT

[@saipratapdannana8048]

your all videos are awesome. why did you stop uploading videos bro ?

[@shamikbhattacharjee7321]

because one of the contributors humblefool unfortunately died.

[@scriptkiddie6151]

This good initiative had a bad end.

[@AbhishekKumar-ff9vg]

FOR PREDECESSOR : - CASE 1 : we will have to find max in left subtree of the given node CASE 2: and when left subtree is not available curr = node_given ; ancs = root ; pred = NULL while ( ancs != NULL ) { if( ancs->data < curr->data ) { pred = ans; ancs = ancs->right; } else ancs = ancs->left; } return ancs;

[@ShivamKhantwal94]

Deserving ❤️❤️

[@musicalive1782]

Good tutorial, but in your else statement you missed succesor = ancestor;

[@harshitadevichopra8097]

nope bro, if we are going right, we dont have to move the succesor... see from 9:22 again... hope u'll get it

[@sandeepkumawat4982]

11:072 Excuse me!!!😂😂

[@rudavathvinod5916]

How to find post order by given data in- order d b e a f c g and pre order a b d e c f g

[@alexrcrew1975]

simply first make the tree after that find post order as simple as that