[algogeeks] tree lock problem

[Balaji Gopalan]

hi
i had this question in my interview:

you are given an n-ary tree.
you are given its root R and a node N.

the problem is to determine if u can "lock" the node N, given the constraints:
1) you cannot lock a node if any of its ancestors is locked.
that is, if you lock a node N, then any node S in the subtree(with root N) cannot be locked till N is unlocked ( N is anscestor of S)
2) similarly you cannot lock a node N if any node S in the subtree rooted at N is locked.
3) no parent pointers in node, you can traverse from root to child only.
4) any representation for a node allowed

Eg:
             1
            /  \
           2   3
          /  \
         4   5

here if 2 is already locked, then we cannot lock 4 or 5
else if 5 is already locked, we cannot lock 2

bye
balaji


--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---