even simpler.. and lesser space. just store in an array the link to all nodes on the tree.. Checking grandparent/parent normally after reaching the node is constant time.
-Rohit On Mon, Feb 8, 2010 at 9:46 PM, saurabh gupta <[email protected]> wrote: > @Manisha can u pls elaborate, ith node index lies in a range ? > > extending Bijlwan's solution, > node numbering on each new level begins by multiplying the index of the > leftmost node in previous level by 2^k and then in incrementing it by one. > and while one checks one shifts by k. > > > On Sat, Feb 6, 2010 at 5:31 PM, Manisha <[email protected]> wrote: > >> One possible soln is: >> Store the k ary- tree nodes in an array such that child of the ith >> node lies in index range from (k*i -1) to (k*i + k -2) range. This >> way child and grandchild index and corresponding items can be found in >> constant time. >> >> On Feb 5, 8:47 pm, Anurag Bhatia <[email protected]> wrote: >> > @Nirmal: Did you find a solution as yet? >> > >> > On Thu, Jan 28, 2010 at 6:40 PM, Nirmal <[email protected]> wrote: >> > > I found this problem in one of the interview form, that it is >> interesting to >> > > discuss >> > >> > > Problem : >> > >> > > There are two nodes given in a tree(not binary tree). Find whether one >> node >> > > is parent/grand parent of other. >> > > order should be O(1). >> > >> > > You are allowed to do any amount of preprocessing .... >> > >> > > -- >> > > 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]<algogeeks%[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]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. > Says he feels all alone in a threatening world where what lies ahead is > vague and uncertain. Doctor says "Treatment is simple. Great clown > Pagliacci is in town tonight. Go and see him. That should pick you up." Man > bursts into tears. Says "But, doctor...I am Pagliacci." > > -- > 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]<algogeeks%[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.
