Operations on tree

Array Hash Table Tree Depth-First Search Breadth-First Search Design

45.0% acceptance

Feb 23, 2026

518

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

struct LockingTree {
  parent: Vec<i32>,
  children: Vec<Vec<usize>>,
  locked_by: Vec<i32>, // 0 means unlocked, >0 means locked by that user
}

impl LockingTree {
  fn new(parent: Vec<i32>) -> Self {
    let n = parent.len();
    let mut children = vec![vec![]; n];
    for i in 1..n {
      children[parent[i] as usize].push(i);
    }
    LockingTree {
      parent,
      children,
      locked_by: vec![0; n],
    }
  }

  fn lock(&mut self, num: i32, user: i32) -> bool {
    let num = num as usize;
    if self.locked_by[num] != 0 {
      return false;
    }
    self.locked_by[num] = user;
    true
  }

  fn unlock(&mut self, num: i32, user: i32) -> bool {
    let num = num as usize;
    if self.locked_by[num] != user {
      return false;
    }
    self.locked_by[num] = 0;
    true
  }

  fn upgrade(&mut self, num: i32, user: i32) -> bool {
    let num = num as usize;
    // Check node is unlocked
    if self.locked_by[num] != 0 {
      return false;
    }
    // Check no locked ancestors
    let mut anc = self.parent[num];
    while anc != -1 {
      if self.locked_by[anc as usize] != 0 {
        return false;
      }
      anc = self.parent[anc as usize];
    }
    // Check at least one locked descendant and unlock all
    if !self.unlock_descendants(num) {
      return false;
    }
    self.locked_by[num] = user;
    true
  }

  fn unlock_descendants(&mut self, node: usize) -> bool {
    let mut found = false;
    // Need to collect children to avoid borrow issues
    let children: Vec<usize> = self.children[node].clone();
    for child in children {
      if self.locked_by[child] != 0 {
        self.locked_by[child] = 0;
        found = true;
      }
      if self.unlock_descendants(child) {
        found = true;
      }
    }
    found
  }
}