#1993

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Operations on Tree

Design a tree data structure that allows locking, unlocking, and upgrading nodes with user-specific actions.

array hash table tree depth first search breadth first search

Problem Statement

You are given a tree with n nodes numbered from 0 to n-1. The structure is represented by an array parent, where parent[i] is the parent of node i. The root node is 0, so parent[0] = -1 as it has no parent. You need to design a data structure that supports locking, unlocking, and upgrading nodes.

The data structure should provide the following methods: lock(num, user), which locks the node num by user user; unlock(num, user), which unlocks node num if it is locked by the same user; and upgrade(num, user), which locks num if it is unlocked and has at least one locked descendant. Your task is to implement the LockingTree class to perform these operations.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["LockingTree", "lock", "unlock", "unlock", "lock", "upgrade", "lock"] [[[-1, 0, 0, 1, 1, 2, 2]], [2, 2], [2, 3], [2, 2], [4, 5], [0, 1], [0, 1]] Output [null, true, false, true, true, true, false]

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.

Solution Approach

Array Representation for Parent-Child Relationships

Utilize the parent array to represent the tree structure, enabling fast access to each node's parent. This allows for an efficient tree traversal when performing operations like upgrades.

Hash Lookup for Lock and Unlock Operations

Implement a hash table to track the lock state of each node, associating each node with the user who has locked it. This provides O(1) lookup time for checking lock/unlock operations.

Efficient Upgrade Logic

During an upgrade operation, recursively check the locked descendants of a node. If any are locked, upgrade the parent node, ensuring the process is fast by leveraging the parent array and hash table.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for each operation is dependent on how the tree is traversed and how efficiently the lock/unlock and upgrade operations are handled using hash lookups. For lock/unlock, it's O(1), while upgrade requires potentially traversing the tree, leading to a time complexity of O(n). Space complexity is O(n) due to the storage of parent relationships and lock states for each node.

What Interviewers Usually Probe

Candidate efficiently designs data structures for dynamic operations on trees.
Look for clear explanations of array and hash table usage to manage state.
Focus on the trade-off between tree traversal and hash lookups for optimized performance.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the tree traversal logic during upgrade operations.
Incorrectly handling lock/unlock state changes across multiple users.
Not considering edge cases, such as trying to unlock a node locked by another user.

Follow-up variants

Add a query function to check if a node is locked.
Allow multiple users to lock the same node with different states.
Optimize for memory usage by using a more compact data structure for large trees.

FAQ

What is the primary pattern for solving the 'Operations on Tree' problem?

The key pattern is array scanning combined with hash lookups to efficiently manage node states in a tree structure.

How do we ensure efficient upgrades in the tree?

Use the parent array for quick traversal and a hash table to track locked nodes, enabling fast upgrades.

What should be the time complexity for lock/unlock operations?

Both lock and unlock operations should run in O(1) time using hash lookups.

How does the parent array contribute to solving this problem?

The parent array provides an efficient way to traverse the tree, helping manage the upgrade logic and track parent-child relationships.

Can the 'Operations on Tree' problem be optimized for larger inputs?

Yes, optimizing the tree traversal for upgrades and ensuring minimal memory usage can make the solution scalable to large inputs.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

class LockingTree:
    def __init__(self, parent: List[int]):
        n = len(parent)
        self.locked = [-1] * n
        self.parent = parent
        self.children = [[] for _ in range(n)]
        for son, fa in enumerate(parent[1:], 1):
            self.children[fa].append(son)

    def lock(self, num: int, user: int) -> bool:
        if self.locked[num] == -1:
            self.locked[num] = user
            return True
        return False

    def unlock(self, num: int, user: int) -> bool:
        if self.locked[num] == user:
            self.locked[num] = -1
            return True
        return False

    def upgrade(self, num: int, user: int) -> bool:
        def dfs(x: int):
            nonlocal find
            for y in self.children[x]:
                if self.locked[y] != -1:
                    self.locked[y] = -1
                    find = True
                dfs(y)

        x = num
        while x != -1:
            if self.locked[x] != -1:
                return False
            x = self.parent[x]

        find = False
        dfs(num)
        if not find:
            return False
        self.locked[num] = user
        return True


# Your LockingTree object will be instantiated and called as such:
# obj = LockingTree(parent)
# param_1 = obj.lock(num,user)
# param_2 = obj.unlock(num,user)
# param_3 = obj.upgrade(num,user)

Continue Practicing

#2368 reachable nodes with restrictions #1261 find elements in a contaminated binary tree #690 employee importance