1993. Operations on Tree

Problem Description

The problem at hand is designing a data structure for a tree, particularly a LockingTree class that supports three distinct operations - lock, unlock, and upgrade for tree nodes. Here's how the operations work:

• lock(num, user): This method attempts to lock the node numbered num for the user with the id user. A node can be locked if it's currently unlocked. If successful, the method returns true; otherwise, it returns false.

• unlock(num, user): This method tries to unlock the node numbered num for the user with the id user. A node can be unlocked if it's currently locked by the same user. If the operation is successful, the method returns true; otherwise, false.

• upgrade(num, user): This method does a bit more. It locks the node numbered num if, and only if, the node is currently unlocked, it has at least one locked descendant by any user, and there are no locked nodes among its ancestors. If these conditions are met and the node is successfully upgraded, the method returns true; otherwise, false.

Each node is identified by an integer from 0 to n-1, where n is the total number of nodes, and parent[i] denotes the parent of the i-th node (with parent[0] = -1 for the root of the tree).

Intuition

The solution is built around the classic tree data structure and additional constructs to handle the locking mechanism.

• Initializing the tree from a parent array involves setting up children lists for each node, so that we have direct access to the descendants of any node. This is done because we frequently need to check the lock status of a node's descendants.

• For locking and unlocking, we simply check or modify the lock status, which can be efficiently represented as an array where each index corresponds to a node and stores the id of the user who locked it or -1 if it's unlocked.

• The upgrade operation is more involved. It requires a check that all ancestors of the node are unlocked and at least one descendant is locked. After confirming an ancestor is unlocked, we need to traverse the subtree of the node to unlock all descendants and then lock the node itself. Depth-first search (DFS) is employed for subtree traversal. We use DFS because it allows us to dive deep into the children and check the necessary conditions efficiently before backtracking.

Implementing these operations while keeping these data structures in sync allows the LockingTree class to simulate the required locking, unlocking, and upgrading mechanism.

Learn more about Tree, Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation of the LockingTree class is designed around a few key components and algorithms. Here's a step-by-step walk-through of the approach:

• Initialization (__init__ method): The constructor takes in a list named parent which represents the parent of each node in the tree. A list of locked statuses is initialized to keep track of which nodes are locked and by whom (represented by user IDs, with -1 signifying an unlocked node). Additionally, a children list is created for each node to facilitate quick access to the node's descendants, which is filled by iterating through the parent list and appending the child nodes correspondingly.

• Lock (lock method): To lock a node, the method checks if the locked status of the node num is -1 (unlocked). If it is, the method updates the locked status to the user ID to indicate that the node is now locked by that user and returns true. If the node is already locked (locked[num] is not -1), the method returns false.

• Unlock (unlock method): To unlock a node, the method checks if the locked status of the node num is equal to the user ID, ensuring it's only unlocked by the user who locked it. If the condition is met, it sets the locked status back to -1 to indicate that the node is unlocked and returns true. If not, it returns false (meaning the node is locked by a different user or already unlocked).

• Upgrade (upgrade method): The upgrade operation is more complex and it is where the depth-first search (DFS) comes into play. Initially, the method traverses the ancestors of the node num to check if any of them are locked; if any are, the method returns false. After checking the ancestors, a DFS is executed starting from node num to visit all its descendants:

  • A helper function dfs is declared within the upgrade method to facilitate recursive traversal.
  • The dfs function iterates over all direct children of a given node.
  • For each child, if the child is locked, it is unlocked (resetting the locked status to -1) and a flag find is set to true to indicate that at least one locked descendant has been found and unlocked.
  • Recursion continues until all descendants are visited.

After DFS, if no locked descendants were found (indicated by find being false), the method returns false since the upgrade would not change anything. If there were locked descendants, node num is then locked for user, and the method returns true.

Using these approaches, all the required operations can be efficiently performed on the LockingTree.

Example Walkthrough

Let's consider a small example to illustrate how LockingTree would work. We'll be working with the following tree represented by the parent array:

1-1, 0, 0, 1, 1, 2, 2

This represents a tree with 7 nodes where:

• Node 0 is the root.
• Nodes 1 and 2 are children of node 0.
• Nodes 3 and 4 are children of node 1.
• Nodes 5 and 6 are children of node 2.

Let's walk through each operation step by step:

Initialization (__init__ method)

We initialize the LockingTree with our parent array. The locked array starts with all nodes unlocked (all values set to -1). Our children would be constructed as lists within a list that represents the children of each node:

1children = [[1, 2], [3, 4], [5, 6], [], [], [], []]
2locked = [-1, -1, -1, -1, -1, -1, -1]

Lock (lock method)

Suppose user 101 wants to lock node 5. Since node 5 is initially unlocked (its value in locked is -1), the lock method updates locked[5] to 101:

1locked = [-1, -1, -1, -1, -1, 101, -1]

The method returns true because we successfully locked node 5.

Unlock (unlock method)

Now, user 101 decides to unlock node 5. We check if locked[5] is 101. Since this check passes, we set locked[5] back to -1:

1locked = [-1, -1, -1, -1, -1, -1, -1]

The method returns true as the node was successfully unlocked.

Upgrade (upgrade method)

The following scenarios may occur during the upgrade operation:

• User 102 wants to upgrade node 1. We look at the ancestors: node 0 is the only ancestor and it is unlocked. Then, we execute DFS from node 1 and find that neither of its descendants (nodes 3 and 4) are locked. Since we have no locked descendants, upgrade returns false.

• User 103 locks node 3 and then wishes to upgrade node 1. It is checked that none of the ancestors are locked. Then, DFS finds that node 3 is locked, so locked[3] is set to -1, and locked[1] is set to 103. After upgrading, the locked status array would be:

1locked = [-1, 103, -1, -1, -1, -1, -1]

The method would return true as the upgrade was successful.

This concludes our walkthrough with a simple example showcasing how the LockingTree class handles lock, unlock, and upgrade operations.

Solution Implementation

Time and Space Complexity

Time Complexity

• __init__(self, parent: List[int]):

  • This method has a time complexity of O(n), where n is the number of nodes in the tree. It's required to initialize the locked, parent, and children lists, where the latter involves appending the children for each node in a single pass (for son, fa in enumerate(parent[1:], 1)).

• lock(self, num: int, user: int) -> bool and unlock(self, num: int, user: int) -> bool:

  • These methods have a constant time complexity, O(1), since they are simply checking and updating an element in the locked list at an index.

• upgrade(self, num: int, user: int) -> bool:

  • The time complexity is O(n + m) where n is the number of ancestors of the node num and m is the total number of descendants of the node num. This is because it traverses up to the root from num and then uses a depth-first search to traverse through all descendants.
  • Worst-case scenario occurs when num is the root or a node high in the tree (O(n) for ancestor check since the tree height could be n in the worst case) and when every node has only one child leading to a depth-first search that includes every node (O(n) for descendant check because you need to visit every node in that case). So, the upper bound on the time complexity becomes O(2n), which simplifies to O(n).

Space Complexity

• __init__(self, parent: List[int]):

  • The space complexity is O(n) due to the storage required for locked, parent, and children lists which all have a length proportional to n, the number of nodes in the tree.

• lock(self, num: int, user: int) -> bool and unlock(self, num: int, user: int) -> bool:

  • Both methods have a constant space complexity, O(1), since no additional space is needed beyond the input parameters and the temporary variables.

• upgrade(self, num: int, user: int) -> bool:

  • A depth-first search is used, which in the worst case can have a call stack size of n in case of a skewed tree, so the space complexity is O(n) where n is the number of nodes in the tree. This is due to the potential call stack depth in the recursive dfs function.

Learn more about how to find time and space complexity quickly using problem constraints.