Tree of Space Locking and Unlocking N-Ary Tree

• Difficulty Level : Hard
• Last Updated : 21 Nov, 2021

Given a world map in the form of Generic M-ary Tree consisting of N nodes and an array queries[], the task is to implement the functions Lock, Unlock and Upgrade for the given tree. For each query in queries[], the functions return true when the operation is performed successfully, otherwise it returns false. The functions are defined as:

X: Name of the node in the tree and will be unique uid: User Id for the person who accesses node X

1. Lock(X, uid): Lock takes exclusive access to the subtree rooted.

• Once Lock(X, uid) succeeds, then lock(A, any user) should fail, where A is a descendant of X.
• Lock(B. any user) should fail where X is a descendant of B.
• Lock operation cannot be performed on a node that is already locked.

2. Unlock(X, uid): To unlock the locked node.

• The unlock reverts what was done by the Lock operation.
• It can only be called on same and unlocked by same uid.

3. UpgradeLock(X, uid): The user uid can upgrade their lock to an ancestor node.

• It is only possible if any ancestor node is only locked by the same user uid.
• The Upgrade should fail if there is any node that is locked by some other uid Y below.

Examples:

Input: N = 7, M = 2, nodes = [World, Asia, Africa, China, India, SouthAfrica, Egypt], queries = [1 China 9, 1 India 9, 3 Asia 9, 2 India 9, 2 Asia 9] Output: true true true false true

Input: N = 3, M = 2, nodes = [World, China, India], queries = [3 India 1, 1 World 9] Output: false true

Question 1 Locking the tree of space 1 You have a world map represented as an M-Ary tree (sample the below) World Asia Africa Lock(X, uid) India China KA MP TN BLR m = 3, N = 121 (number of nodes in a complete 3-ary tree) You need to define three operations on it