Hi,
This is one approach to it:
1) Go to the first node in inorder traversal. Let the pointer be LP.
(Push the intermediate nodes to Lstack while doing this )
2) Go to the last node in inorder traversal. Let the pointer be RP.
(Push the intermediate nodes to Rstack while doing this )
while(LP->data < RP->data){
LP = inordersuccessor(LP,Lstack)
// gets inorder successor and modifies Lstack accordingly
RP = inorderpredecessor(RP,Rstack)
// gets inorder predecessor and modifies Rstack accordingly
Lprev = LP
Rprev = RP;
}
if(LP->data = RP->data){ // even number of elements
retrun LP->data;
}else{
return Lprev->data + Rprev->data / 2
}
Time: O(n)
Memory: 2 * O ( log n) average
Thanks,
Balaji.
On Sun, Mar 27, 2011 at 7:17 PM, bittu <[email protected]> wrote:
> @all
>
> wake up geeks
>
>
> Thanks
> Shashank
>
> --
> 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.
>
>
--
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.
