1993. Operations On Tree - Explanation

1. Depth First Search

Intuition

We need to simulate a locking system on a tree structure. The key insight is that lock and unlock are simple O(1) operations since they only check and modify a single node. The upgrade operation is more complex: it requires checking all ancestors (no locks allowed) and all descendants (at least one lock required, then unlock all).

For the ancestor check, we traverse up the parent chain. For the descendant check and unlock, we use dfs to visit all nodes in the subtree, counting and clearing any locks.

Algorithm

Initialization: Build a child adjacency list from the parent array and create a locked array to track which user (if any) has locked each node.
lock(num, user): If the node is unlocked (locked[num] == 0), set locked[num] = user and return true. Otherwise return false.
unlock(num, user): If locked[num] equals user, set it to 0 and return true. Otherwise return false.
upgrade(num, user):
- Walk up the parent chain from num. If any ancestor is locked, return false.
- Run dfs on the subtree rooted at num: count locked descendants and unlock them.
- If at least one descendant was locked, lock num with user and return true. Otherwise return false.

class LockingTree:

    def __init__(self, parent: List[int]):
        self.parent = parent
        self.child = [[] for _ in range(len(parent))]
        self.locked = [0] * len(parent)
        for node in range(1, len(parent)):
            self.child[parent[node]].append(node)

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

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

    def upgrade(self, num: int, user: int) -> bool:
        node = num
        while node != -1:
            if self.locked[node]:
                return False
            node = self.parent[node]

        def dfs(node):
            lockedCount = 0
            if self.locked[node]:
                lockedCount += 1
                self.locked[node] = 0

            for nei in self.child[node]:
                lockedCount += dfs(nei)
            return lockedCount

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

Time & Space Complexity

Time complexity:
- $O(n)$ time for initialization.
- $O(1)$ time for each $lock()$ and $unlock()$ function call.
- $O(n)$ time for each $upgrade()$ function call.
Space complexity: $O(n)$

2. Breadth First Search

Intuition

This solution replaces the recursive dfs for the descendant traversal with an iterative BFS using a queue. The logic remains identical: lock and unlock are O(1) operations, while upgrade requires ancestor and descendant checks.

BFS processes nodes level by level, which can be more cache-friendly in some cases and avoids potential stack overflow issues with very deep trees.

Algorithm

Initialization: Same as dfs, build child lists and initialize the locked array.
lock and unlock: Same O(1) checks and updates.
upgrade(num, user):
- Check ancestors by walking up the parent chain.
- Use a queue to traverse all descendants, counting and unlocking any locked nodes.
- If lockedCount > 0, lock num for user and return true.

class LockingTree:

    def __init__(self, parent: List[int]):
        self.parent = parent
        self.child = [[] for _ in range(len(parent))]
        self.locked = [0] * len(parent)
        for node in range(1, len(parent)):
            self.child[parent[node]].append(node)

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

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

    def upgrade(self, num: int, user: int) -> bool:
        node = num
        while node != -1:
            if self.locked[node]:
                return False
            node = self.parent[node]

        lockedCount, q = 0, deque([num])
        while q:
            node = q.popleft()
            if self.locked[node]:
                self.locked[node] = 0
                lockedCount += 1
            q.extend(self.child[node])

        if lockedCount:
            self.locked[num] = user
            return True
        return False

Time & Space Complexity

Time complexity:
- $O(n)$ time for initialization.
- $O(1)$ time for each $lock()$ and $unlock()$ function call.
- $O(n)$ time for each $upgrade()$ function call.
Space complexity: $O(n)$

3. Iterative DFS

Intuition

This approach converts the recursive dfs into an iterative version using an explicit stack. This is useful when you want to avoid recursion overhead or potential stack overflow on very large trees, while maintaining the depth-first traversal order.

The core logic for all three operations remains unchanged from the recursive dfs solution.

Algorithm

Initialization: Build child adjacency lists and initialize the locked array.
lock and unlock: Same O(1) checks.
upgrade(num, user):
- Traverse ancestors to ensure none are locked.
- Use a stack to perform iterative dfs on descendants.
- Pop nodes, check if locked, unlock if so, and push children.
- If any descendants were locked, lock num and return true.

class LockingTree:

    def __init__(self, parent: List[int]):
        self.parent = parent
        self.child = [[] for _ in range(len(parent))]
        self.locked = [0] * len(parent)
        for node in range(1, len(parent)):
            self.child[parent[node]].append(node)

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

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

    def upgrade(self, num: int, user: int) -> bool:
        node = num
        while node != -1:
            if self.locked[node]:
                return False
            node = self.parent[node]

        lockedCount, stack = 0, [num]
        while stack:
            node = stack.pop()
            if self.locked[node]:
                self.locked[node] = 0
                lockedCount += 1
            stack.extend(self.child[node])

        if lockedCount:
            self.locked[num] = user
            return True
        return False

Time & Space Complexity

Time complexity:
- $O(n)$ time for initialization.
- $O(1)$ time for each $lock()$ and $unlock()$ function call.
- $O(n)$ time for each $upgrade()$ function call.
Space complexity: $O(n)$

Common Pitfalls

Not Checking All Ancestors for Upgrade

The upgrade operation requires that no ancestor of the node is locked. Checking only the immediate parent is insufficient. You must traverse the entire path from the node to the root, verifying each ancestor is unlocked before proceeding.

Forgetting to Unlock Descendants Before Locking

When upgrade succeeds, all locked descendants must be unlocked before locking the current node. Some solutions lock the node first, which means when traversing descendants, the node itself gets incorrectly counted or unlocked. Process descendants completely before modifying the current node.

Returning True When No Descendants Are Locked

The upgrade operation requires at least one locked descendant. Even if all other conditions are met (node unlocked, ancestors unlocked), if no descendant is locked, the operation must return false. Always verify the locked descendant count is greater than zero before returning success.