@sunny finding lca in logn is fine, but how can we traverse the path in
logn.. ?

On Fri, Jun 10, 2011 at 3:50 PM, sunny agrawal <sunny816.i...@gmail.com>wrote:

> @ross if a parent pointer is there lca can be found in lgn
> and path can be traversed in lgn too
> why it cannot be lgn
> what is the problem ??
>
>
> On Fri, Jun 10, 2011 at 3:06 PM, sunny agrawal <sunny816.i...@gmail.com>wrote:
>
>> thats why i mentioned x OR z and i m considering parent pointer :)
>> without parent pointer both solutions will be O(n) :)
>>
>>
>> On Fri, Jun 10, 2011 at 3:02 PM, Harshal <hc4...@gmail.com> wrote:
>>
>>> @Sunny
>>> I am assuming that the tree is rooted. There is no 'parent' pointer.
>>>                   A
>>>               /      \
>>>            B         C*
>>>           /               \
>>>        D*                 F*
>>>                           /  \
>>>                         J      K
>>>                        /  \
>>>                            M*
>>>
>>> suppose x=D, y=C, z=F
>>> According to you, finding the lca of x and z=> A
>>> Now y lies on path from lca to z, but it doesn't lie on path from x to z.
>>> Am I missing something?
>>>
>>>
>>> On Fri, Jun 10, 2011 at 2:50 PM, sunny agrawal 
>>> <sunny816.i...@gmail.com>wrote:
>>>
>>>> but that will be O(n) i think
>>>>
>>>>
>>>> On Fri, Jun 10, 2011 at 2:38 PM, Harshal <hc4...@gmail.com> wrote:
>>>>
>>>>> can be solved using dfs.
>>>>>
>>>>>
>>>>> On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal <
>>>>> sunny816.i...@gmail.com> wrote:
>>>>>
>>>>>> find common Ancestor of both. see if y lies on path from x or z to
>>>>>> this ancestor
>>>>>> O(lgn)
>>>>>>
>>>>>>
>>>>>> On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal <
>>>>>> goyal.aanch...@gmail.com> wrote:
>>>>>>
>>>>>>> There is a binary tree(Not a BST) in which you are given three nodes
>>>>>>> x,y,z .Write a function which finds whether y lies in the path b/w x
>>>>>>> and z.
>>>>>>>
>>>>>>> --
>>>>>>> Regards,*
>>>>>>> Aanchal Goyal*.
>>>>>>>
>>>>>>>  --
>>>>>>> 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.
>>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Sunny Aggrawal
>>>>>> B-Tech IV year,CSI
>>>>>> Indian Institute Of Technology,Roorkee
>>>>>>
>>>>>>
>>>>>>  --
>>>>>> 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.
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Harshal Choudhary,
>>>>> III Year B.Tech CSE,
>>>>> NIT Surathkal, Karnataka, India.
>>>>>
>>>>>
>>>>>
>>>>>  --
>>>>> 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.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Sunny Aggrawal
>>>> B-Tech IV year,CSI
>>>> Indian Institute Of Technology,Roorkee
>>>>
>>>>  --
>>>> 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.
>>>>
>>>
>>>
>>>
>>> --
>>> Harshal Choudhary,
>>> III Year B.Tech CSE,
>>> NIT Surathkal, Karnataka, India.
>>>
>>>
>>>  --
>>> 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.
>>>
>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> 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.
>



-- 
Regards,*
Aanchal Goyal*.

-- 
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.

Reply via email to