I didn't check the correctness of it. I think this is how the count field might improve the time. 1.Whenever you lock a node, increase the count field of all its ancestors and the current node by 1. 2.Similarly when you unlock it, decrease the count field of all its ancestors and the current node by 1. 3. When you are about to lock a node, you need to check two things - i)whether its count field has value 0 which implies none of the subtree nodes (including the current one) are locked, and ii)check that none of my ancestors are locked (this can be done by keeping a count of number of locked nodes, which can be incremented whenever we see one, the recursion in DFS will take care of maintaining it by getting back to the old one when the recursion ends).
This will allow you to lock a node in the first DFS search itself. If you need the algo, ping me.. --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
