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 iduser
. A node can be locked if it's currently unlocked. If successful, the method returnstrue
; otherwise, it returnsfalse
. -
unlock(num, user): This method tries to unlock the node numbered
num
for the user with the iduser
. A node can be unlocked if it's currently locked by the same user. If the operation is successful, the method returnstrue
; 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 returnstrue
; 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).
Flowchart Walkthrough
Let's analyze the algorithm for LeetCode problem 1993, "Operations on Tree," by navigating through the Flowchart. We will break down the consideration for each node in the flowchart:
-
Is it a graph?
- Yes: The tree structure can be represented as a graph where each node is a vertex, and each edge represents a direct relationship (parent-child in this case).
-
Is it a tree?
- Yes: The structure described in the problem is explicitly a tree, representing hierarchical relationships.
Now, with DFS selected based on the tree identification, we proceed with using Depth-First Search (DFS) to explore or manipulate the tree. DFS is appropriate for typical operations on trees such as searching, updating, or manipulating because it efficiently traverses all nodes starting from the root or any given node, exploring as far as possible along each branch before backtracking.
Conclusion: The flowchart suggests using DFS due to the problem involving a tree structure. This will be efficient for exploring or manipulating different attributes or operations specific to each node, like locking, unlocking, etc.
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 namedparent
which represents the parent of each node in the tree. A list oflocked
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, achildren
list is created for each node to facilitate quick access to the node's descendants, which is filled by iterating through theparent
list and appending the child nodes correspondingly. -
Lock (
lock
method): To lock a node, the method checks if thelocked
status of the nodenum
is-1
(unlocked). If it is, the method updates thelocked
status to theuser
ID to indicate that the node is now locked by that user and returnstrue
. If the node is already locked (locked[num]
is not-1
), the method returnsfalse
. -
Unlock (
unlock
method): To unlock a node, the method checks if thelocked
status of the nodenum
is equal to theuser
ID, ensuring it's only unlocked by the user who locked it. If the condition is met, it sets thelocked
status back to-1
to indicate that the node is unlocked and returnstrue
. If not, it returnsfalse
(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 nodenum
to check if any of them are locked; if any are, the method returnsfalse
. After checking the ancestors, a DFS is executed starting from nodenum
to visit all its descendants:- A helper function
dfs
is declared within theupgrade
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 flagfind
is set totrue
to indicate that at least one locked descendant has been found and unlocked. - Recursion continues until all descendants are visited.
- A helper function
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
and2
are children of node0
. - Nodes
3
and4
are children of node1
. - Nodes
5
and6
are children of node2
.
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 node1
. We look at the ancestors: node0
is the only ancestor and it is unlocked. Then, we execute DFS from node1
and find that neither of its descendants (nodes3
and4
) are locked. Since we have no locked descendants,upgrade
returnsfalse
. -
User
103
locks node3
and then wishes to upgrade node1
. It is checked that none of the ancestors are locked. Then, DFS finds that node3
is locked, solocked[3]
is set to-1
, andlocked[1]
is set to103
. After upgrading, thelocked
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
1class LockingTree:
2 def __init__(self, parent: List[int]):
3 # Initialize the LockingTree with the number of nodes and their parent relationships
4 self.num_nodes = len(parent)
5 # -1 represents an unlocked node, and a non-negative number represents the user that locked it
6 self.locked_status = [-1] * self.num_nodes
7 self.parents = parent
8 # Create a list to track the children of each node
9 self.children = [[] for _ in range(self.num_nodes)]
10 # Filling the children relationships
11 for child_index, parent_index in enumerate(parent[1:], 1):
12 self.children[parent_index].append(child_index)
13
14 def lock(self, node: int, user: int) -> bool:
15 # Lock the node if it is not currently locked, then return True. Otherwise, return False.
16 if self.locked_status[node] == -1:
17 self.locked_status[node] = user
18 return True
19 return False
20
21 def unlock(self, node: int, user: int) -> bool:
22 # Unlock the node if it is currently locked by the same user, then return True. Otherwise, return False.
23 if self.locked_status[node] == user:
24 self.locked_status[node] = -1
25 return True
26 return False
27
28 def upgrade(self, node: int, user: int) -> bool:
29 # Recursive function to unlock all descendants of a node
30 def unlock_descendants(curr_node: int):
31 nonlocal found_locked_descendant
32 for child in self.children[curr_node]:
33 if self.locked_status[child] != -1:
34 self.locked_status[child] = -1
35 found_locked_descendant = True
36 unlock_descendants(child)
37
38 # Ascend from current node to root, ensuring none of the ancestors are locked
39 ancestor = node
40 while ancestor != -1:
41 if self.locked_status[ancestor] != -1:
42 return False
43 ancestor = self.parents[ancestor]
44
45 # At this point, none of the ancestors are locked. Check if we have locked descendants.
46 found_locked_descendant = False
47 unlock_descendants(node)
48 if not found_locked_descendant:
49 return False
50
51 # If there are locked descendants and no locked ancestors, lock current node and return True.
52 self.locked_status[node] = user
53 return True
54
55# Your LockingTree object will be instantiated and called as such:
56# obj = LockingTree(parent)
57# param_1 = obj.lock(node, user)
58# param_2 = obj.unlock(node, user)
59# param_3 = obj.upgrade(node, user)
60
1class LockingTree {
2 private int[] locks;
3 private int[] parents;
4 private List<Integer>[] children;
5
6 // Constructor to initialize the LockingTree object with the parent-child relationship
7 public LockingTree(int[] parent) {
8 int nodeCount = parent.length;
9 locks = new int[nodeCount];
10 this.parents = parent;
11 children = new List[nodeCount];
12
13 // Initialize the locks array where -1 signifies that node is unlocked
14 Arrays.fill(locks, -1);
15 // Initialize the children list array for each node
16 Arrays.setAll(children, i -> new ArrayList<>());
17
18 // Construct the tree by populating the children list for each node
19 for (int i = 1; i < nodeCount; i++) {
20 children[parent[i]].add(i);
21 }
22 }
23
24 // Tries to lock the node with a given user id
25 public boolean lock(int node, int userId) {
26 if (locks[node] == -1) {
27 locks[node] = userId;
28 return true;
29 }
30 return false; // The node was already locked
31 }
32
33 // Tries to unlock the node with the user id if the user holds the lock
34 public boolean unlock(int node, int userId) {
35 if (locks[node] == userId) {
36 locks[node] = -1;
37 return true;
38 }
39 return false; // The node is locked by a different user or is already unlocked
40 }
41
42 // Attempts to upgrade a lock at the node: lock the node if it and all its ancestors are unlocked, while unlocking all of its descendants
43 public boolean upgrade(int node, int userId) {
44 int currentNode = node;
45 // Check all ancestors to make sure they're unlocked
46 while (currentNode != -1) {
47 if (locks[currentNode] != -1) {
48 return false;
49 }
50 currentNode = parents[currentNode];
51 }
52
53 boolean[] hasLockedDescendants = new boolean[1];
54 // Recursively checks and unlocks all descendants that are locked
55 dfsUnlockDescendants(node, hasLockedDescendants);
56
57 if (!hasLockedDescendants[0]) {
58 return false; // There's no locked descendant to unlock
59 }
60
61 // Perform the upgrade by locking the current node
62 locks[node] = userId;
63 return true;
64 }
65
66 // Helper method for a depth-first search from a node to unlock all descendants
67 private void dfsUnlockDescendants(int node, boolean[] hasLockedDescendants) {
68 for (int child : children[node]) {
69 if (locks[child] != -1) {
70 locks[child] = -1; // Unlock the child node
71 hasLockedDescendants[0] = true;
72 }
73 dfsUnlockDescendants(child, hasLockedDescendants); // Continue to search in the subtree
74 }
75 }
76}
77
1#include <vector>
2#include <functional>
3
4class LockingTree {
5public:
6 // Constructor to initialize the LockingTree object with a given parent vector.
7 LockingTree(std::vector<int>& parent) {
8 int n = parent.size();
9 locked.resize(n, -1); // Initialize all nodes as unlocked
10 this->parent = parent;
11 children.resize(n); // Resize to create a children list for each node
12 for (int i = 1; i < n; ++i) {
13 // Assign children to their corresponding parents
14 children[parent[i]].push_back(i);
15 }
16 }
17
18 // Try to lock the given node (num) with user ID. Return true if successful.
19 bool lock(int num, int user) {
20 if (locked[num] == -1) { // If not already locked
21 locked[num] = user; // Lock the node with the user ID
22 return true;
23 }
24 return false; // Node is already locked
25 }
26
27 // Try to unlock the given node (num) with user ID. Return true if successful.
28 bool unlock(int num, int user) {
29 if (locked[num] == user) { // If the node is locked by this user
30 locked[num] = -1; // Unlock the node
31 return true;
32 }
33 return false; // Node is locked by another user or not locked
34 }
35
36 // Upgrade a lock on a node if conditions are satisfied. Return true if successful.
37 bool upgrade(int num, int user) {
38 // Check that all ancestors are unlocked
39 int currentNode = num;
40 while (currentNode != -1) {
41 if (locked[currentNode] != -1) {
42 return false; // An ancestor is locked; cannot upgrade
43 }
44 currentNode = parent[currentNode]; // Move to the parent
45 }
46 // Now check for locked descendants
47 bool hasLockedDescendant = false;
48 std::function<void(int)> dfs = [&](int node) {
49 // Depth-first search to visit each descendant
50 for (int child : children[node]) {
51 if (locked[child] != -1) {
52 // Found a locked descendant
53 hasLockedDescendant = true;
54 // Unlock descendant
55 locked[child] = -1;
56 }
57 // Recursively visit children
58 dfs(child);
59 }
60 };
61 dfs(num); // Start DFS from the node
62
63 if (!hasLockedDescendant) {
64 // No locked descendants; cannot upgrade
65 return false;
66 }
67 // Lock the node with user ID
68 locked[num] = user;
69 return true; // The upgrade was successful
70 }
71
72private:
73 std::vector<int> locked; // Keeps track of locked nodes with user IDs (-1 if unlocked)
74 std::vector<int> parent; // Stores parent of each node
75 std::vector<std::vector<int>> children; // Adjacency list for node children
76};
77
78/**
79 * Your LockingTree object will be instantiated and called as such:
80 * LockingTree* obj = new LockingTree(parent);
81 * bool param_1 = obj->lock(num,user);
82 * bool param_2 = obj->unlock(num,user);
83 * bool param_3 = obj->upgrade(num,user);
84 */
85
1// Define the structure for locking management.
2let locked: number[];
3let parent: number[];
4let children: number[][];
5
6// Initialize the locking management structure with a parent array.
7function initLockingTree(parentArray: number[]): void {
8 const n = parentArray.length;
9 locked = Array(n).fill(-1);
10 parent = parentArray;
11 children = Array(n)
12 .fill(0)
13 .map(() => []);
14 for (let i = 1; i < n; i++) {
15 children[parentArray[i]].push(i);
16 }
17}
18
19// Attempt to lock a node with a given user.
20function lock(num: number, user: number): boolean {
21 if (locked[num] === -1) {
22 locked[num] = user;
23 return true;
24 }
25 return false;
26}
27
28// Attempt to unlock a node with a given user.
29function unlock(num: number, user: number): boolean {
30 if (locked[num] === user) {
31 locked[num] = -1;
32 return true;
33 }
34 return false;
35}
36
37// Attempt to upgrade a node with a given user.
38function upgrade(num: number, user: number): boolean {
39 let x = num;
40 // Check that all ancestors are unlocked.
41 for (; x !== -1; x = parent[x]) {
42 if (locked[x] !== -1) {
43 return false;
44 }
45 }
46 let hasLockedDescendants = false;
47
48 // Depth-First Search to find if there are any locked descendants.
49 const dfs = (node: number): void => {
50 for (const child of children[node]) {
51 if (locked[child] !== -1) {
52 locked[child] = -1;
53 hasLockedDescendants = true;
54 }
55 dfs(child);
56 }
57 };
58
59 dfs(num);
60
61 if (!hasLockedDescendants) {
62 return false;
63 }
64
65 // If conditions are met lock the node.
66 locked[num] = user;
67 return true;
68}
69
70// Sample Usage:
71// initLockingTree([<parentArray>]);
72// let isLocked = lock(<num>, <user>);
73// let isUnlocked = unlock(<num>, <user>);
74// let isUpgraded = upgrade(<num>, <user>);
75
Time and Space Complexity
Time Complexity
-
__init__(self, parent: List[int])
:- This method has a time complexity of
O(n)
, wheren
is the number of nodes in the tree. It's required to initialize thelocked
,parent
, andchildren
lists, where the latter involves appending the children for each node in a single pass (for son, fa in enumerate(parent[1:], 1)
).
- This method has a time complexity of
-
lock(self, num: int, user: int) -> bool
andunlock(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 thelocked
list at an index.
- These methods have a constant time complexity,
-
upgrade(self, num: int, user: int) -> bool
:- The time complexity is
O(n + m)
wheren
is the number of ancestors of the nodenum
andm
is the total number of descendants of the nodenum
. This is because it traverses up to the root fromnum
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 ben
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 becomesO(2n)
, which simplifies toO(n)
.
- The time complexity is
Space Complexity
-
__init__(self, parent: List[int])
:- The space complexity is
O(n)
due to the storage required forlocked
,parent
, andchildren
lists which all have a length proportional ton
, the number of nodes in the tree.
- The space complexity is
-
lock(self, num: int, user: int) -> bool
andunlock(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.
- Both methods have a constant space complexity,
-
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 isO(n)
wheren
is the number of nodes in the tree. This is due to the potential call stack depth in the recursivedfs
function.
- A depth-first search is used, which in the worst case can have a call stack size of
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell