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 <[email protected]> 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 <
> [email protected]> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
