What Deoki answered in valid for non-leaf node. Consider this tree: 3 / \ 4 5 / \ 6 7
According to Deoki's answer, 7's in-order successor is 4, which not correct. the answer should be 3. Here is the proper method (for leaf node only), Following Deoki's answer for non-leaf: - keep a stack in which you keep adding the left child (if there is any) at the node. - in case you don't have a left child, pop the last parent. and push the right child. Repeat above process. - when you hit the node you are searching for and is a leaf node, then just pop the last element from stack. That will the inorder successor. e.g in above tree, in-order successor of 7. from start stack will be |3| -> | 4 | push(3->left) = 4 | 3 | -> | 6 | push(4->left) = 6 | 4 | | 3 | -> no left of 6, and pop 6, and check right. -> no right of 6, pop next element, i.e. 4 -> push (4->right) | 7 | | 3 | -> Found 7 and '7' is a leaf node, thus in-order successor is pop (next element) = 3 Hope that's clear. On 12 August 2011 12:34, Deoki Nandan <deok...@gmail.com> wrote: > if given node has right subtree then its inorder successor will be left > most child of given node's right child. if given node does not have right > child the its successor will be its parent > > > On Fri, Aug 12, 2011 at 11:28 AM, Priyanka Goel < > priyankatheinvinci...@gmail.com> wrote: > >> How to find the in-order successor of a given node in a binary search tree >> where each node has a link to its parent. pl explain logic to solve it.. >> ( Pl dnt give solution of doing in order traversal and storing it in >> array.) >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > **With Regards > Deoki Nandan Vishwakarma > > * > * > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- ___________________________________________________________________________________________________________ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers <=> Save Trees -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.