@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 <pgo...@gmail.com> 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 <abhati...@gmail.com> wrote: > > @Nirmal: Did you find a solution as yet? > > > > On Thu, Jan 28, 2010 at 6:40 PM, Nirmal <nirm...@gmail.com> 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 algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > > > 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@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.
