Skip to main content
Talentd

Operations on Tree - Solution & Explanation

MediumArrayHash TableTreeDepth-First Search14 min readAsked at: Amazon, Google, Juspay
Practice this problem

Problem Statement

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) 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.length
  • 2 <= n <= 2000
  • 0 <= parent[i] <= n - 1 for i != 0
  • parent[0] == -1
  • 0 <= num <= n - 1
  • 1 <= user <= 104
  • parent represents a valid tree.
  • At most 2000 calls in total will be made to lock, unlock, and upgrade.

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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaC++

Java

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Traversal for Tree OperationsLock/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 TrackingO(h + k)O(n)Better when frequent upgrade operations require repeated ancestor and subtree validation.

Video Solution

Operations on Tree - Leetcode Biweekly Contest - 1993 - Python • NeetCode • 15,074 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Operations on Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Throne Inheritance