1993. Operations on Tree

MediumTreeDepth-First SearchBreadth-First SearchDesignArrayHash Table
Leetcode Link

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).

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:

  1. 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).

  2. 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 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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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, 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:

children = [[1, 2], [3, 4], [5, 6], [], [], [], []]
locked = [-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:

locked = [-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:

locked = [-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:

locked = [-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), 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of these properties could exist for a graph but not a tree?

Recommended Readings

Everything About Trees

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

DFS Fundamentals

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

BFS Fundamentals

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

Want a Structured Path to Master System Design Too? Don’t Miss This!