In this guide, you will get 1993. Operations on Tree LeetCode Solution with the best time and space complexity. The solution to Operations on Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given a tree with n nodes numbered from 0 to n – 1 in the form of a parent array parent where parent[i] is the parent of the ith node. The root of the tree is node 0, so parent[0] = -1 since it has no parent. You want to design a data structure that allows users to lock, unlock, and upgrade nodes in the tree.
The data structure should support the following functions:
Lock: Locks the given node for the given user and prevents other users from locking the same node. You may only lock a node using this function if the node is unlocked.
Unlock: Unlocks the given node for the given user. You may only unlock a node using this function if it is currently locked by the same user.
Upgrade: Locks the given node for the given user and unlocks all of its descendants regardless of who locked it. You may only upgrade a node if all 3 conditions are true:
The node is unlocked,
It has at least one locked descendant (by any user), and
It does not have any locked ancestors.
Implement the LockingTree class:
LockingTree(int[] parent) initializes the data structure with the parent array.
lock(int num, int user) returns true if it is possible for the user with id user to lock the node num, or false otherwise. If it is possible, the node num will become locked by the user with id user.
unlock(int num, int user) returns true if it is possible for the user with id user to unlock the node num, or false otherwise. If it is possible, the node num will become unlocked.
upgrade(int num, int user) returns true if it is possible for the user with id user to upgrade the node num, or false otherwise. If it is possible, the node num will be upgraded.
Explanation
LockingTree lockingTree = new LockingTree([-1, 0, 0, 1, 1, 2, 2]);
lockingTree.lock(2, 2); // return true because node 2 is unlocked.
// Node 2 will now be locked by user 2.
lockingTree.unlock(2, 3); // return false because user 3 cannot unlock a node locked by user 2.
lockingTree.unlock(2, 2); // return true because node 2 was previously locked by user 2.
// Node 2 will now be unlocked.
lockingTree.lock(4, 5); // return true because node 4 is unlocked.
// Node 4 will now be locked by user 5.
lockingTree.upgrade(0, 1); // return true because node 0 is unlocked and has at least one locked descendant (node 4).
// Node 0 will now be locked by user 1 and node 4 will now be unlocked.
lockingTree.lock(0, 1); // return false because node 0 is already locked.
Constraints:
n == parent.length
2 <= n <= 2000
0 <= parent[i] <= n – 1 for i != 0
parent[0] == -1
0 <= num <= n – 1
1 <= user <= 104
parent represents a valid tree.
At most 2000 calls in total will be made to lock, unlock, and upgrade.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1993. Operations on Tree LeetCode Solution in C++
struct Node {
vector<int> children;
int lockedBy = -1;
};
class LockingTree {
public:
LockingTree(vector<int>& parent) : parent(parent) {
nodes.resize(parent.size());
for (int i = 1; i < parent.size(); ++i)
nodes[parent[i]].children.push_back(i);
}
bool lock(int num, int user) {
if (nodes[num].lockedBy != -1)
return false;
return nodes[num].lockedBy = user;
}
bool unlock(int num, int user) {
if (nodes[num].lockedBy != user)
return false;
return nodes[num].lockedBy = -1;
}
bool upgrade(int num, int user) {
if (nodes[num].lockedBy != -1)
return false;
if (!anyLockedDescendant(num))
return false;
// Walk up the hierarchy to ensure that there are no locked ancestors.
for (int i = num; i != -1; i = parent[i])
if (nodes[i].lockedBy != -1)
return false;
unlockDescendants(num);
return nodes[num].lockedBy = user;
}
private:
const vector<int> parent;
vector<Node> nodes;
bool anyLockedDescendant(int i) {
return nodes[i].lockedBy != -1 ||
ranges::any_of(nodes[i].children, [this](const int child) {
return anyLockedDescendant(child);
});
}
void unlockDescendants(int i) {
nodes[i].lockedBy = -1;
for (const int child : nodes[i].children)
unlockDescendants(child);
}
}; /* code provided by PROGIEZ */
1993. Operations on Tree LeetCode Solution in Java
class Node {
public List<Integer> children = new ArrayList<>();
public int lockedBy = -1;
}
class LockingTree {
public LockingTree(int[] parent) {
this.parent = parent;
nodes = new Node[parent.length];
for (int i = 0; i < parent.length; ++i)
nodes[i] = new Node();
for (int i = 1; i < parent.length; ++i)
nodes[parent[i]].children.add(i);
}
public boolean lock(int num, int user) {
if (nodes[num].lockedBy != -1)
return false;
nodes[num].lockedBy = user;
return true;
}
public boolean unlock(int num, int user) {
if (nodes[num].lockedBy != user)
return false;
nodes[num].lockedBy = -1;
return true;
}
public boolean upgrade(int num, int user) {
if (nodes[num].lockedBy != -1)
return false;
if (!anyLockedDescendant(num))
return false;
// Walk up the hierarchy to ensure that there are no locked ancestors.
for (int i = num; i != -1; i = parent[i])
if (nodes[i].lockedBy != -1)
return false;
unlockDescendants(num);
nodes[num].lockedBy = user;
return true;
}
private int[] parent;
private Node[] nodes;
private boolean anyLockedDescendant(int i) {
return nodes[i].lockedBy != -1 ||
nodes[i].children.stream().anyMatch(child -> anyLockedDescendant(child));
}
private void unlockDescendants(int i) {
nodes[i].lockedBy = -1;
for (final int child : nodes[i].children)
unlockDescendants(child);
}
} // code provided by PROGIEZ
1993. Operations on Tree LeetCode Solution in Python
class Node:
def __init__(self):
self.children: list[int] = []
self.lockedBy = -1
class LockingTree:
def __init__(self, parent: list[int]):
self.parent = parent
self.nodes = [Node() for _ in range(len(parent))]
for i in range(1, len(parent)):
self.nodes[parent[i]].children.append(i)
def lock(self, num: int, user: int) -> bool:
if self.nodes[num].lockedBy != -1:
return False
self.nodes[num].lockedBy = user
return True
def unlock(self, num: int, user: int) -> bool:
if self.nodes[num].lockedBy != user:
return False
self.nodes[num].lockedBy = -1
return True
def upgrade(self, num: int, user: int) -> bool:
if self.nodes[num].lockedBy != -1:
return False
if not self._anyLockedDescendant(num):
return False
# Walk up the hierarchy to ensure that there are no locked ancestors.
i = num
while i != -1:
if self.nodes[i].lockedBy != -1:
return False
i = self.parent[i]
self._unlockDescendants(num)
self.nodes[num].lockedBy = user
return True
def _anyLockedDescendant(self, i: int) -> bool:
return (self.nodes[i].lockedBy != -1 or
any(self._anyLockedDescendant(child)
for child in self.nodes[i].children))
def _unlockDescendants(self, i: int) -> None:
self.nodes[i].lockedBy = -1
for child in self.nodes[i].children:
self._unlockDescendants(child) # code by PROGIEZ
