LeetCode Problem 1993

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Tree, Depth-First Search, Breadth-First Search, Design

Solution

LeetCode 1993 - Operations on Tree

Problem Understanding

The problem asks us to design a mutable tree-based data structure that supports three operations: lock, unlock, and upgrade. Each node in the tree may either be unlocked or locked by exactly one user. The operations must follow strict rules about when a node may change state.

The input tree is represented using a parent array. For every node i, parent[i] gives the parent of that node. Since the structure is guaranteed to be a valid tree, every node except the root has exactly one parent, and there are no cycles. The root node is always node 0, and its parent is -1.

The lock(num, user) operation attempts to lock a node for a user. A node can only be locked if it is currently unlocked. If successful, the node becomes associated with that user.

The unlock(num, user) operation attempts to unlock a node. A node can only be unlocked by the same user who originally locked it. If another user attempts to unlock it, the operation fails.

The upgrade(num, user) operation is the most complicated. It simultaneously locks the target node and unlocks all locked descendants. However, it can only succeed if all three conditions hold:

1. The node itself is currently unlocked.
2. At least one descendant of the node is locked.
3. None of the node's ancestors are locked.

If these conditions are satisfied, every locked descendant becomes unlocked, and the target node becomes locked by the requesting user.

The constraints are important when deciding how sophisticated the implementation needs to be. The tree size is at most 2000 nodes, and the total number of operations is also at most 2000. These limits are relatively small. This means an O(n) traversal during operations is completely acceptable, because even in the worst case we only perform a few million operations overall.

Several edge cases are important:

• Attempting to lock an already locked node must fail.
• Attempting to unlock a node using the wrong user ID must fail.
• An upgrade operation must fail if the node itself is already locked.
• An upgrade operation must fail if no descendants are locked.
• An upgrade operation must fail if any ancestor is locked.
• Descendants locked by different users must all be unlocked during upgrade.
• The root node has no ancestors, so ancestor checking must stop correctly.

The problem guarantees that the tree is valid and that all node indices are within bounds.

Approaches

Brute Force Approach

A direct brute-force implementation would repeatedly scan the entire tree structure during every operation.

For the lock and unlock operations, this is straightforward because we only need to inspect the current node state.

For the upgrade operation, the brute-force strategy would:

1. Walk upward through parents to verify no ancestor is locked.
2. Traverse the entire subtree rooted at the target node to locate locked descendants.
3. Unlock every locked descendant.
4. Lock the current node.

This approach is correct because it explicitly checks every rule required by the problem statement. Since every relevant ancestor and descendant is inspected, no invalid upgrade can occur.

Even though this is called a brute-force approach, it is actually fast enough for the given constraints because n <= 2000. However, without organizing children relationships in advance, subtree traversals become inefficient because we would repeatedly search for children by scanning the whole parent array.

Optimal Approach

The key observation is that the tree structure never changes. We can preprocess the parent array into an adjacency list of children. This allows efficient descendant traversal using DFS or BFS.

We maintain:

• The original parent array for ancestor traversal.
• A children adjacency list for subtree traversal.
• A locked array storing which user currently owns each node, or -1 if unlocked.

The improvement comes from organizing the tree so descendant operations become natural graph traversals instead of repeated global scans.

Since the constraints are small, we do not need advanced data structures like segment trees or Euler tours. A clean DFS-based solution is both efficient and easy to reason about.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) worst case across repeated subtree scans	O(n)	Repeatedly scans parent array to locate descendants
Optimal	O(n) per operation	O(n)	Uses adjacency list for efficient descendant traversal

Algorithm Walkthrough

1. Store the parent array directly inside the class because ancestor traversal requires repeatedly moving upward from a node.
2. Build a children adjacency list during initialization. For every node i, append i to children[parent[i]]. This allows fast traversal of descendants.
3. Maintain a locked array where:

• locked[i] = -1 means node i is unlocked.
• locked[i] = userId means node i is locked by that user.

4. For the lock(num, user) operation:

• Check whether locked[num] is already occupied.
• If it is already locked, return False.
• Otherwise store the user ID and return True.

5. For the unlock(num, user) operation:

• Verify the node is currently locked by the same user.
• If not, return False.
• Otherwise reset the node to -1 and return True.

6. For the upgrade(num, user) operation:

• First verify the node itself is unlocked.
• Then walk upward through ancestors using the parent array.
• If any ancestor is locked, return False.

7. Traverse all descendants using DFS or BFS:

• Track whether at least one locked descendant exists.
• Whenever a locked descendant is found, unlock it immediately.

8. After traversal:

• If no locked descendant was found, return False.
• Otherwise lock the current node with the given user and return True.

Why it works

The algorithm works because every operation directly enforces the rules described in the problem statement.

The lock and unlock operations only modify a node when the required ownership conditions hold.

For upgrade, the algorithm guarantees correctness by checking all ancestors before any modification occurs, ensuring no locked ancestor exists. The descendant traversal guarantees every locked descendant is discovered and unlocked. Because the target node is locked only after these conditions succeed, the final state always satisfies the required upgrade semantics.

Python Solution

from typing import List
from collections import deque

class LockingTree:

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

    def lock(self, num: int, user: int) -> bool:
        if self.locked[num] != -1:
            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] = -1
        return True

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

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

        found_locked_descendant = False

        queue = deque([num])

        while queue:
            current = queue.popleft()

            for child in self.children[current]:
                queue.append(child)

                if self.locked[child] != -1:
                    found_locked_descendant = True
                    self.locked[child] = -1

        if not found_locked_descendant:
            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)

The constructor preprocesses the tree into a children adjacency list. This makes descendant traversal efficient because we can directly access all children of a node instead of searching the parent array repeatedly.

The locked array acts as the central state tracker. Using -1 for unlocked nodes keeps checks simple and efficient.

The lock method only succeeds if the node is currently unlocked. Otherwise it immediately returns False.

The unlock method verifies ownership before unlocking. This ensures only the locking user can release the node.

The upgrade method has three phases. First it checks whether the current node is unlocked. Second it walks upward through ancestors to ensure none are locked. Third it performs BFS traversal over descendants to locate and unlock all locked nodes. If no locked descendant exists, the operation fails. Otherwise the current node becomes locked.

Go Solution

package main

type LockingTree struct {
	parent   []int
	children [][]int
	locked   []int
}

func Constructor(parent []int) LockingTree {
	n := len(parent)

	children := make([][]int, n)

	for i := 1; i < n; i++ {
		p := parent[i]
		children[p] = append(children[p], i)
	}

	locked := make([]int, n)

	for i := 0; i < n; i++ {
		locked[i] = -1
	}

	return LockingTree{
		parent:   parent,
		children: children,
		locked:   locked,
	}
}

func (this *LockingTree) Lock(num int, user int) bool {
	if this.locked[num] != -1 {
		return false
	}

	this.locked[num] = user
	return true
}

func (this *LockingTree) Unlock(num int, user int) bool {
	if this.locked[num] != user {
		return false
	}

	this.locked[num] = -1
	return true
}

func (this *LockingTree) Upgrade(num int, user int) bool {
	if this.locked[num] != -1 {
		return false
	}

	ancestor := this.parent[num]

	for ancestor != -1 {
		if this.locked[ancestor] != -1 {
			return false
		}
		ancestor = this.parent[ancestor]
	}

	foundLockedDescendant := false

	queue := []int{num}

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		for _, child := range this.children[current] {
			queue = append(queue, child)

			if this.locked[child] != -1 {
				foundLockedDescendant = true
				this.locked[child] = -1
			}
		}
	}

	if !foundLockedDescendant {
		return false
	}

	this.locked[num] = user
	return true
}

The Go implementation follows the same logical structure as the Python version. Slices are used for adjacency lists and queues. Since Go does not provide a built-in deque, a slice-based queue implementation is sufficient for these constraints.

The locked slice uses -1 to represent unlocked nodes, exactly like the Python solution. Integer overflow is not a concern because all values are very small.

Worked Examples

Example 1

Input:

parent = [-1,0,0,1,1,2,2]

Tree structure:

        0
      /   \
     1     2
    / \   / \
   3   4 5   6

Operation 1

lock(2, 2)

Node	Locked By
0	-1
1	-1
2	2
3	-1
4	-1
5	-1
6	-1

Result: true

Operation 2

unlock(2, 3)

Node 2 is locked by user 2, not user 3.

Result: false

Operation 3

unlock(2, 2)

Node	Locked By
0	-1
1	-1
2	-1
3	-1
4	-1
5	-1
6	-1

Result: true

Operation 4

lock(4, 5)

Node	Locked By
0	-1
1	-1
2	-1
3	-1
4	5
5	-1
6	-1

Result: true

Operation 5

upgrade(0, 1)

Ancestor check:

• Node 0 has no ancestors.

Descendant traversal:

• Node 4 is found locked.
• Node 4 becomes unlocked.

Then node 0 becomes locked by user 1.

Node	Locked By
0	1
1	-1
2	-1
3	-1
4	-1
5	-1
6	-1

Result: true

Operation 6

lock(0, 1)

Node 0 is already locked.

Result: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) per operation	Upgrade may traverse ancestors and descendants
Space	O(n)	Children list and lock state arrays

The lock and unlock operations run in constant time because they only inspect one node. The upgrade operation may visit all ancestors and all descendants, which in the worst case touches every node once. Since n <= 2000, this is fully acceptable.

Test Cases

# Example 1
tree = LockingTree([-1, 0, 0, 1, 1, 2, 2])

assert tree.lock(2, 2) is True      # lock unlocked node
assert tree.unlock(2, 3) is False   # wrong user cannot unlock
assert tree.unlock(2, 2) is True    # correct user unlocks
assert tree.lock(4, 5) is True      # another node locked
assert tree.upgrade(0, 1) is True   # upgrade succeeds
assert tree.lock(0, 1) is False     # already locked

# Example 2 style scenario
tree = LockingTree([-1, 0, 0, 1, 1])

assert tree.lock(3, 10) is True     # descendant locked
assert tree.upgrade(1, 20) is True  # upgrade unlocks descendant
assert tree.lock(3, 30) is True     # descendant now unlocked

# Upgrade fails because no locked descendants
tree = LockingTree([-1, 0, 0])

assert tree.upgrade(0, 1) is False  # no locked descendant

# Upgrade fails because ancestor locked
tree = LockingTree([-1, 0, 1])

assert tree.lock(0, 1) is True      # lock ancestor
assert tree.lock(2, 2) is True      # lock descendant
assert tree.upgrade(1, 3) is False  # ancestor locked

# Unlocking unlocked node
tree = LockingTree([-1, 0])

assert tree.unlock(1, 1) is False   # node already unlocked

# Single descendant unlock during upgrade
tree = LockingTree([-1, 0, 1, 2])

assert tree.lock(3, 7) is True
assert tree.upgrade(1, 8) is True
assert tree.lock(3, 9) is True      # descendant successfully unlocked earlier

# Multiple descendants locked by different users
tree = LockingTree([-1, 0, 0, 1, 1])

assert tree.lock(3, 1) is True
assert tree.lock(4, 2) is True
assert tree.upgrade(1, 3) is True   # both descendants unlocked

Test	Why
Basic lock and unlock	Verifies normal state transitions
Wrong user unlock	Ensures ownership rules are enforced
Upgrade with locked descendants	Verifies successful upgrade behavior
Upgrade without locked descendants	Confirms required condition checking
Locked ancestor during upgrade	Ensures ancestor validation works
Multiple descendant unlocks	Verifies upgrade unlocks all descendants
Re-lock after upgrade	Confirms descendants were actually unlocked

Edge Cases

One important edge case occurs when attempting to unlock a node using the wrong user ID. This is a common source of mistakes because it is easy to check only whether the node is locked, instead of verifying ownership. The implementation correctly handles this by requiring locked[num] == user before unlocking.

Another important edge case is performing an upgrade on a node whose ancestor is already locked. A naive implementation might only inspect descendants and forget ancestor validation entirely. The solution explicitly walks upward through the parent chain before making any modifications, ensuring upgrades cannot violate locking hierarchy rules.

A third important edge case happens when an upgrade is requested on a node that has no locked descendants. Even if the node itself is unlocked and all ancestors are unlocked, the operation must still fail. The BFS traversal tracks whether at least one locked descendant was encountered using the found_locked_descendant flag. If none are found, the method returns False without changing the tree state.