We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Operations on Tree

Difficulty: Medium

Problem Description

You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array where parent[i] is the parent of the i-th 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 if it is unlocked.
  • Unlock: Unlocks the given node for the given user. You may only unlock a node 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 them. You may only upgrade a node if it is unlocked, it has at least one locked descendant, and it does not have any locked ancestors.

Key Insights

  • The tree structure can be represented using a parent-child relationship based on an array.
  • Each node can be locked by only one user at a time, requiring careful management of user IDs for locking and unlocking.
  • The upgrade operation necessitates tracking both descendants and ancestors to ensure the conditions are met before upgrading.

Space and Time Complexity

Time Complexity: O(n) for initialization and O(h) for lock, unlock, and upgrade operations (where h is the height of the tree). Space Complexity: O(n) for storing the tree structure and user states.

Solution

To solve this problem, we will use an adjacency list to represent the tree and maintain additional data structures for tracking locked nodes and their corresponding user IDs. The main operations will involve traversing the tree to check conditions for locking, unlocking, and upgrading nodes.

The tree will be built from the parent array, creating a list of children for each node. For locking and unlocking, we will check the current state of the node and the user ID to determine if the operation can proceed. For upgrading, we will check if the node is unlocked, has at least one locked descendant, and does not have any locked ancestors.

Code Solutions

class LockingTree:
    def __init__(self, parent):
        self.parent = parent
        self.children = [[] for _ in range(len(parent))]
        self.locked = {}
        self.locked_user = {}
        for child in range(1, len(parent)):
            self.children[parent[child]].append(child)

    def lock(self, num, user):
        if num in self.locked:
            return False
        self.locked[num] = True
        self.locked_user[num] = user
        return True

    def unlock(self, num, user):
        if num not in self.locked or self.locked_user[num] != user:
            return False
        del self.locked[num]
        del self.locked_user[num]
        return True

    def upgrade(self, num, user):
        if num in self.locked:
            return False
        if self.has_locked_ancestor(num):
            return False
        if not self.has_locked_descendant(num):
            return False
        self.lock(num, user)
        self.unlock_descendants(num)
        return True

    def has_locked_ancestor(self, num):
        while num != -1:
            if num in self.locked:
                return True
            num = self.parent[num]
        return False

    def has_locked_descendant(self, num):
        if num in self.locked:
            return True
        for child in self.children[num]:
            if self.has_locked_descendant(child):
                return True
        return False

    def unlock_descendants(self, num):
        if num in self.locked:
            del self.locked[num]
            del self.locked_user[num]
        for child in self.children[num]:
            self.unlock_descendants(child)
← Back to All Questions