The first from the root to the node N. Here you will get the path from root to N. Just go along the path and see whether there is any locked node. If there is a locked node then you cannot lock node N.
Next you do a complete DFS of the subtree starting with node N. If any of the lower nodes are locked you cannot lock node N.
Time complexity : O(nodes)
-Dhyanesh
On 3/24/06, Balaji Gopalan <[EMAIL PROTECTED]> wrote:
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
-~----------~----~----~----~------~----~------~--~---
