D
DevExCode

LeetCode 1993: Operations on Tree Solution

Master LeetCode problem 1993 (Operations on Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To implement the LockingTree class, we can use a combination of a tree data structure and some additional bookkeeping to keep track of locked nodes and their relationships. We can use a map to store the locked nodes along with the user who locked them. Additionally, we can store the parent array to quickly check for locked ancestors and locked descendants.

  1. Lock: We check if the node is unlocked and there are no locked ancestors. If so, we lock the node.
  2. Unlock: We check if the node is locked by the same user. If so, we unlock the node.
  3. Upgrade: We check if the node is unlocked, has at least one locked descendant, and has no locked ancestors. If so, we lock the node and unlock all descendants.

Time Complexity:

  • Lock: O(1)
  • Unlock: O(1)
  • Upgrade: O(n) where n is the number of nodes in the tree

Space Complexity: O(n) where n is the number of nodes in the tree

Solution Code

class LockingTree {
    int[] parent;
    Map<Integer, Integer> lockedNodes; // node -> user
    Map<Integer, Set<Integer>> descendants; // node -> set of descendants

    public LockingTree(int[] parent) {
        this.parent = parent;
        this.lockedNodes = new HashMap<>();
        this.descendants = new HashMap<>();
    }

    public boolean lock(int num, int user) {
        if (lockedNodes.containsKey(num) || hasLockedAncestor(num)) {
            return false;
        }
        lockedNodes.put(num, user);
        return true;
    }

    public boolean unlock(int num, int user) {
        if (lockedNodes.containsKey(num) && lockedNodes.get(num) == user) {
            lockedNodes.remove(num);
            return true;
        }
        return false;
    }

    public boolean upgrade(int num, int user) {
        if (!lockedNodes.containsKey(num) && hasLockedDescendant(num) && !hasLockedAncestor(num)) {
            lockedNodes.put(num, user);
            unlockDescendants(num);
            return true;
        }
        return false;
    }

    private boolean hasLockedAncestor(int num) {
        int curr = num;
        while (parent[curr] != -1) {
            curr = parent[curr];
            if (lockedNodes.containsKey(curr)) {
                return true;
            }
        }
        return false;
    }

    private boolean hasLockedDescendant(int num) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(num);

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (lockedNodes.containsKey(curr) && curr != num) {
                return true;
            }
            visited.add(curr);
            for (int child : descendants.getOrDefault(curr, new HashSet<>())) {
                if (!visited.contains(child)) {
                    queue.offer(child);
                }
            }
        }
        return false;
    }

    private void unlockDescendants(int num) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(num);

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            lockedNodes.remove(curr);
            visited.add(curr);
            for (int child : descendants.getOrDefault(curr, new HashSet<>())) {
                if (!visited.contains(child)) {
                    queue.offer(child);
                }
            }
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1993 (Operations on Tree)?

This page provides optimized solutions for LeetCode problem 1993 (Operations on Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1993 (Operations on Tree)?

The time complexity for LeetCode 1993 (Operations on Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1993 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1993 in Java, C++, or Python.

Back to LeetCode Solutions