Locking Unlocking of N-ary Tree

Given an n-ary tree of resources arranged hierarchically such that the height of the tree is O(log N) where N is a total number of nodes (or resources). A process needs to lock a resource node in order to use it. But a node cannot be locked if any of its descendant or ancestor is locked.


Following operations are required for a given resource node:


Lock(string X, int id):

1. if X is already locked then you cannot lock it, so return false

2. if any of its descendants is locked, you cannot lock it, so return false

3. if any of its ancestors is locked, you cannot lock it, so return false

4. If none of the above conditions are met, lock X with id


Unlock(string X, int id):

1. if X is not locked return false

2. if X is locked by some different id, then return false

3. otherwise unlock and return true


UpgradeLock(string X, int id):

1. If X is locked return false

2. If it has no locked Descendents return false

3. If it has locked descendants by more than one id then return false

4. If the above condition doesn't satisfy then unlock every locked descendants and lock X



Solution

Code in C++