Watch 6 video solutions for Operations on Tree, a medium level problem involving Array, Hash Table, Tree. This walkthrough by NeetCode has 14,680 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of the ith node. The root of the tree is node 0, so parent[0] = -1 since it has no parent. You want to design a data structure that allows users to lock, unlock, and upgrade nodes in the tree.
The data structure should support the following functions:
Implement the LockingTree class:
LockingTree(int[] parent) initializes the data structure with the parent array.lock(int num, int user) returns true if it is possible for the user with id user to lock the node num, or false otherwise. If it is possible, the node num will become locked by the user with id user.unlock(int num, int user) returns true if it is possible for the user with id user to unlock the node num, or false otherwise. If it is possible, the node num will become unlocked.upgrade(int num, int user) returns true if it is possible for the user with id user to upgrade the node num, or false otherwise. If it is possible, the node num will be upgraded.
Example 1:
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.length2 <= n <= 20000 <= parent[i] <= n - 1 for i != 0parent[0] == -10 <= num <= n - 11 <= user <= 104parent represents a valid tree.2000 calls in total will be made to lock, unlock, and upgrade.Problem Overview: You need to design a data structure that supports three operations on a tree: lock, unlock, and upgrade. A node can be locked by a user, unlocked by the same user, and upgraded only if none of its ancestors are locked and at least one descendant is locked. The challenge is efficiently checking ancestor and descendant states during these operations.
Approach 1: DFS Traversal for Tree Operations (O(n) per upgrade, O(h) ancestor check)
This approach builds the tree from the parent array and stores the lock status for each node. When performing operations, you explicitly traverse the structure. For ancestor validation, iterate upward using the parent pointer until reaching the root. For descendant checks during upgrade, run a Depth-First Search or Breadth-First Search starting from the target node to detect locked descendants and unlock them if needed.
The key idea is direct traversal instead of maintaining extra metadata. The lock and unlock operations run in O(1) time, while the upgrade operation may scan the subtree, giving O(n) time in the worst case with O(n) space for the adjacency list. This solution is simple to implement and works well when the number of upgrade operations is small.
Approach 2: Using Parent and Child Tracking (O(h + k) operations)
This design improves efficiency by storing additional relationships between nodes. Along with the parent array, maintain a list of children for each node and track lock ownership in a hash structure. Checking ancestors becomes a quick upward traversal of height h. Descendant verification can iterate through children recursively and unlock nodes as required.
The advantage is clearer control over subtree traversal and easier management of node relationships. The upgrade operation runs in O(k), where k is the number of nodes in the subtree being inspected, and space complexity remains O(n). This approach fits naturally with problems involving tree design and hierarchical state management.
Recommended for interviews: Interviewers typically expect the DFS-based design. It demonstrates that you understand tree traversal, ancestor checks, and state management. Starting with the straightforward traversal approach shows clear reasoning. Optimizing the design with structured parent/child tracking highlights deeper understanding of data structure design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Traversal for Tree Operations | Lock/Unlock: O(1), Upgrade: O(n) | O(n) | Best for simple implementations and interview settings where clarity matters more than heavy optimization. |
| Using Parent and Child Tracking | O(h + k) | O(n) | Better when frequent upgrade operations require repeated ancestor and subtree validation. |