⚡Flashcard Drill➔
NeetCode #453LC-1993MediumTrees
← Back to All Problems

#453 · #1993 · Operations on Tree(树上的操作)

📌 Problem Statement & Constraints

Design a locking tree with n nodes numbered 0..n-1 and a parent array (parent[i] is the parent of i, -1 for the root). Implement lock(num, user), unlock(num, user) and upgrade(num, user). upgrade succeeds only when the node is unlocked, no ancestor is locked, and at least one descendant is locked; it then unlocks all locked descendants and locks the node. Constraints: 1 <= n <= 2000; at most 2000 calls.

💡 Core Algorithmic Approaches

  1. Keep a locked array mapping each node to the locking user, or 0 for unlocked.
  2. lock and unlock are O(1) checks against that array.
  3. upgrade needs two traversals: walk up the parent chain to verify no locked ancestor, and walk down the children to collect locked descendants.
  4. A children adjacency list makes the downward walk efficient; the descendant unlocks happen during that walk.

💻 Benchmark Python3 Implementation

class LockingTree:
    def __init__(self, parent: List[int]):
        from collections import defaultdict
        self.parent = parent
        self.locked = [0] * len(parent)    # node -> user, 0 means unlocked
        self.children = defaultdict(list)
        for i, p in enumerate(parent):
            if p != -1:
                self.children[p].append(i)

    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                   # only the locker may unlock
        self.locked[num] = 0
        return True

    def upgrade(self, num: int, user: int) -> bool:
        if self.locked[num]:
            return False                   # must be unlocked
        # 1) no locked ancestor
        p = self.parent[num]
        while p != -1:
            if self.locked[p]:
                return False
            p = self.parent[p]
        # 2) at least one locked descendant, and unlock them all
        found = False
        st = list(self.children[num])
        while st:
            c = st.pop()
            if self.locked[c]:
                self.locked[c] = 0
                found = True
            st.extend(self.children[c])
        if not found:
            return False                   # nothing to upgrade from
        self.locked[num] = user
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(depth) for lock/unlock, O(n) for upgrade in the worst case.
💾 Space Complexity
O(n) for the locked array and the adjacency list.

⚠️ Interview Pitfalls & Follow-ups

  • Unlocking descendants before confirming the upgrade: the ancestor check must pass first, and the descendant scan must find at least one locked node; otherwise the unlocks would corrupt the state.
  • Allowing the locker's identity to be ignored in unlock: only the user who locked a node may unlock it.
  • Checking only the immediate parent: the whole ancestor chain must be free.
  • Forgetting to lock the node itself after a successful upgrade: the operation both unlocks descendants and locks the node.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems