for every node , store a struct , such that it has parent and grand parent. store this node as key and value as struct in hash table.
-rahul On Tue, Mar 9, 2010 at 7:19 PM, Rohit Saraf <[email protected]>wrote: > 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]<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.
