Operations on Tree solution and explanation
Google
4 more videos on this problem
Operations on Tree - Leetcode Biweekly Contest - 1993 - PythonNeetCode · 10:56 · 15K views
Leetcode Biweekly Contest 60 | 1993. Operations on Tree(Medium) in EnglishCompetitive Somya · 6:59 · 1K views
LeetCode 1993. Operations on TreeHappy Coding · 16:11 · 912 views
1993. Operations on Tree - Daily Leetcode (Day 63)yeetcode · 8:21 · 677 views
1993. Operations on Tree (Leetcode Medium)Programming Live with Larry · 26:43 · 390 views
The problem
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:
- Lock: Locks the given node for the given user and prevents other users from locking the same node. You may only lock a node using this function if the node is unlocked.
- Unlock: Unlocks the given node for the given user. You may only unlock a node using this function if it is currently locked by the same user.
- Upgrade: Locks the given node for the given user and unlocks all of its descendants regardless of who locked it. You may only upgrade a node if all 3 conditions are true:
- The node is unlocked,
- It has at least one locked descendant (by any user), and
- It does not have any locked ancestors.
Implement the LockingTree class:
LockingTree(int[] parent)initializes the data structure with the parent array.lock(int num, int user)returnstrueif it is possible for the user with iduserto lock the nodenum, orfalseotherwise. If it is possible, the nodenumwill become locked by the user with iduser.unlock(int num, int user)returnstrueif it is possible for the user with iduserto unlock the nodenum, orfalseotherwise. If it is possible, the nodenumwill become unlocked.upgrade(int num, int user)returnstrueif it is possible for the user with iduserto upgrade the nodenum, orfalseotherwise. If it is possible, the nodenumwill 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 - 1fori != 0parent[0] == -10 <= num <= n - 11 <= user <= 104parentrepresents a valid tree.- At most
2000calls in total will be made tolock,unlock, andupgrade.
Approach overview
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 1: DFS Traversal for Tree Operations
In this approach, we use recursive Depth First Search (DFS) to handle tree operations. The idea is to keep track of locked nodes using an array, allowing quick updates and checks. For the 'upgrade' operation, we ensure that the target node is unlocked and it has at least one locked descendant. We achieve this by recursively examining descendants while also ensuring no ancestors are locked.
class LockingTree:
def __init__(self, parent):
self.parent = parent
self.n = len(parent)
self.locked = [-1] * self.n
def lock(self, num, user):
if self.locked[num] == -1:
self.locked[num] = user
return True
return False
def unlock(self, num, user):
if self.locked[num] == user:
self.locked[num] = -1
return True
return False
def upgrade(self, num, user):
if self.locked[num] != -1:
return False
# Check if there are any locked ancestors
current = num
while current != -1:
if self.locked[current] != -1:
return False
current = self.parent[current]
# Collect locked descendants and unlock them
def dfs(node):
has_locked_descendant = False
for child in range(self.n):
if self.parent[child] == node:
if self.locked[child] != -1:
self.locked[child] = -1
has_locked_descendant = True
has_locked_descendant |= dfs(child)
return has_locked_descendant
if not dfs(num):
return False
# Lock the current node
self.locked[num] = user
return Trueclass LockingTree {
constructor(parent) {
this.parent = parent;
this.n = parent.length;
this.locked = Array(this.n).fill(-1);
}
lock(num, user) {
if (this.locked[num] === -1) {
this.locked[num] = user;
return true;
}
return false;
}
unlock(num, user) {
if (this.locked[num] === user) {
this.locked[num] = -1;
return true;
}
return false;
}
upgrade(num, user) {
if (this.locked[num] !== -1) return false;
// Check for any locked ancestors
let current = num;
while (current !== -1) {
if (this.locked[current] !== -1) return false;
current = this.parent[current];
}
// Unlock descendants and check if there is any locked
const dfs = (node) => {
let hasLockedDescendant = false;
for (let child = 0; child < this.n; child++) {
if (this.parent[child] === node) {
if (this.locked[child] !== -1) {
this.locked[child] = -1;
hasLockedDescendant = true;
}
hasLockedDescendant = dfs(child) || hasLockedDescendant;
}
}
return hasLockedDescendant;
};
if (!dfs(num)) return false;
this.locked[num] = user;
return true;
}
}This Python solution uses a simple tree traversal method to perform lock/unlock operations and complex upgrade operations. It first ensures the node to be upgraded is unlocked and has no locked ancestors. Then it checks for any locked descendants and unlocks them, finally locking the target node for the upgrade.
Time Complexity: O(N) in worst case for upgrade operation due to DFS traversal. Space Complexity: O(N) where N is the number of nodes, to keep track of locks and the recursion stack.
Approach 2: Using Parent and Child Tracking
This approach involves explicitly maintaining a list of children for each node to enable efficient descendant operations. Besides storing locked states, we also keep a list of children for each node, which simplifies descendant traversal, making tree operations like upgrade potentially quicker by directly accessing children.
import java.util.ArrayList;
import java.util.List;
class LockingTree {
private int[] parent;
private int[] locked;
private List<Integer>[] children;
public LockingTree(int[] parent) {
this.parent = parent;
this.locked = new int[parent.length];
this.children = new ArrayList[parent.length];
for (int i = 0; i < parent.length; i++) {
this.children[i] = new ArrayList<>();
}
for (int i = 1; i < parent.length; i++) {
this.children[parent[i]].add(i);
}
}
public boolean lock(int num, int user) {
if (locked[num] == 0) {
locked[num] = user;
return true;
}
return false;
}
public boolean unlock(int num, int user) {
if (locked[num] == user) {
locked[num] = 0;
return true;
}
return false;
}
public boolean upgrade(int num, int user) {
if (locked[num] != 0) return false;
// Check any locked ancestor
int temp = num;
while (temp != -1) {
if (locked[temp] != 0) return false;
temp = parent[temp];
}
// Unlock children
boolean hasLockedDescendant = unlockDescendants(num);
if (!hasLockedDescendant) return false;
// Lock the current node
locked[num] = user;
return true;
}
private boolean unlockDescendants(int node) {
boolean hasLocked = false;
for (int child : children[node]) {
if (locked[child] != 0) {
locked[child] = 0;
hasLocked = true;
}
if (unlockDescendants(child)) hasLocked = true;
}
return hasLocked;
}
}#include <vector>
#include <unordered_map>
using namespace std;
class LockingTree {
public:
vector<int> parent;
vector<int> locked;
vector<vector<int>> children;
LockingTree(vector<int>& parent) : parent(parent), locked(parent.size(), -1) {
children.resize(parent.size());
for (int i = 1; i < parent.size(); ++i) {
children[parent[i]].push_back(i);
}
}
bool lock(int num, int user) {
if (locked[num] == -1) {
locked[num] = user;
return true;
}
return false;
}
bool unlock(int num, int user) {
if (locked[num] == user) {
locked[num] = -1;
return true;
}
return false;
}
bool upgrade(int num, int user) {
if (locked[num] != -1) return false;
// Check locked ancestors
int node = num;
while (node != -1) {
if (locked[node] != -1) return false;
node = parent[node];
}
// Unlock descendants and check
bool hasLockedDescendant = unlockDescendants(num);
if (!hasLockedDescendant) return false;
locked[num] = user;
return true;
}
private:
bool unlockDescendants(int node) {
bool hasLocked = false;
for (int child : children[node]) {
if (locked[child] != -1) {
locked[child] = -1;
hasLocked = true;
}
if (unlockDescendants(child)) hasLocked = true;
}
return hasLocked;
}
};This Java solution uses an additional children list for each node to facilitate child traversal easily. By storing references to each node's children, we can more efficiently implement and verify upgrade conditions.
Time Complexity: O(N) where N is the total number of nodes when checking and unlocking all descendants. Space Complexity: O(N) for maintaining the array and child lists.
Approach 3: Default Approach
class LockingTree {
private locked: number[];
private parent: number[];
private children: number[][];
constructor(parent: number[]) {
const n = parent.length;
this.locked = Array(n).fill(-1);
this.parent = parent;
this.children = Array(n)
.fill(0)
.map(() => []);
for (let i = 1; i < n; i++) {
this.children[parent[i]].push(i);
}
}
lock(num: number, user: number): boolean {
if (this.locked[num] === -1) {
this.locked[num] = user;
return true;
}
return false;
}
unlock(num: number, user: number): boolean {
if (this.locked[num] === user) {
this.locked[num] = -1;
return true;
}
return false;
}
upgrade(num: number, user: number): boolean {
let x = num;
for (; x !== -1; x = this.parent[x]) {
if (this.locked[x] !== -1) {
return false;
}
}
let find = false;
const dfs = (x: number) => {
for (const y of this.children[x]) {
if (this.locked[y] !== -1) {
this.locked[y] = -1;
find = true;
}
dfs(y);
}
};
dfs(num);
if (!find) {
return false;
}
this.locked[num] = user;
return true;
}
}
/**
* Your LockingTree object will be instantiated and called as such:
* var obj = new LockingTree(parent)
* var param_1 = obj.lock(num,user)
* var param_2 = obj.unlock(num,user)
* var param_3 = obj.upgrade(num,user)
*/type LockingTree struct {
locked []int
parent []int
children [][]int
}
func Constructor(parent []int) LockingTree {
n := len(parent)
locked := make([]int, n)
for i := range locked {
locked[i] = -1
}
children := make([][]int, n)
for i := 1; i < n; i++ {
children[parent[i]] = append(children[parent[i]], i)
}
return LockingTree{locked, parent, children}
}
func (this *LockingTree) Lock(num int, user int) bool {
if this.locked[num] == -1 {
this.locked[num] = user
return true
}
return false
}
func (this *LockingTree) Unlock(num int, user int) bool {
if this.locked[num] == user {
this.locked[num] = -1
return true
}
return false
}
func (this *LockingTree) Upgrade(num int, user int) bool {
x := num
for ; x != -1; x = this.parent[x] {
if this.locked[x] != -1 {
return false
}
}
find := false
var dfs func(int)
dfs = func(x int) {
for _, y := range this.children[x] {
if this.locked[y] != -1 {
find = true
this.locked[y] = -1
}
dfs(y)
}
}
dfs(num)
if !find {
return false
}
this.locked[num] = user
return true
}
/**
* Your LockingTree object will be instantiated and called as such:
* obj := Constructor(parent);
* param_1 := obj.Lock(num,user);
* param_2 := obj.Unlock(num,user);
* param_3 := obj.Upgrade(num,user);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| DFS Traversal for Tree Operations | Time Complexity: O(N) in worst case for upgrade operation due to DFS traversal. Space Complexity: O(N) where N is the number of nodes, to keep track of locks and the recursion stack. |
| Using Parent and Child Tracking | Time Complexity: O(N) where N is the total number of nodes when checking and unlocking all descendants. Space Complexity: O(N) for maintaining the array and child lists. |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Operations on Tree easy or hard?
Operations on Tree is considered a medium difficulty problem. The individual operations are straightforward, but correctly handling ancestor and descendant constraints during the upgrade operation requires careful tree traversal and state management.
Operations on Tree Python/Java solution
Python solutions typically store children in adjacency lists and use recursive DFS for descendant checks. Java implementations often use arrays and lists to maintain parent-child relationships while tracking lock states with integer arrays or hash maps.
How to solve Operations on Tree in O(n)?
Build the tree using the parent array and maintain a list of children for each node. When performing an upgrade, first check ancestors by walking up the parent pointers. Then run DFS or BFS on the subtree to confirm at least one locked descendant and unlock all of them. This traversal ensures the operation finishes in O(n) time in the worst case.
What is the best approach for Operations on Tree?
The most practical approach uses DFS traversal with a parent array and adjacency list of children. Ancestors are checked by walking up the parent chain, and descendants are scanned using DFS or BFS. The upgrade operation runs in O(n) worst-case time because the entire subtree may need to be inspected and unlocked.
Is Operations on Tree asked at Google/Amazon/Meta?
Tree design and state management problems like Operations on Tree appear in interviews at large tech companies including Amazon, Google, and Meta. They test understanding of tree traversal, hierarchical constraints, and designing efficient operations on structured data.
What data structure is used in Operations on Tree?
The problem primarily uses a tree represented with a parent array and adjacency lists for children. Additional structures like arrays or hash maps store lock ownership for each node. DFS or BFS traversal is used to validate descendant conditions during upgrade operations.
What is the time complexity of Operations on Tree?
Lock and unlock operations run in O(1) time because they only update the state of a single node. The upgrade operation can take O(n) time in the worst case since it may traverse all descendants of a node to verify and unlock them. Space complexity is O(n) to store the tree structure and lock state.