@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 <[email protected]>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 <[email protected]> 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 >> <[email protected]>wrote: >> >>> but that will be O(n) i think >>> >>> >>> On Fri, Jun 10, 2011 at 2:38 PM, Harshal <[email protected]> wrote: >>> >>>> can be solved using dfs. >>>> >>>> >>>> On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal <[email protected] >>>> > 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 < >>>>> [email protected]> 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 [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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> 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 [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. >>>>> >>>> >>>> >>>> >>>> -- >>>> 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 [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. >>>> >>> >>> >>> >>> -- >>> 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 [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. >>> >> >> >> >> -- >> 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 [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. >> > > > > -- > 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 [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.
