The Infamous
"Tree of Space" Problem

class TreeNode {
  int id;
  TreeNode parent;
  List<TreeNode> children;
  boolean isLocked;
  int lockedBy; // user ID who locked this node
}

Why this works: Store parent pointers to quickly traverse upward for ancestor checks.

boolean hasLockedAncestor(TreeNode node) {
  TreeNode curr = node.parent;
  while (curr != null) {
    if (curr.isLocked) return true;
    curr = curr.parent;
  }
  return false;
}

Why this works: Walk up the tree to root — O(h) complexity. Store parent pointers for fast traversal.

// Maintain a count of locked descendants for each node
Map<TreeNode, Integer> lockedDescendantCount;

boolean hasLockedDescendant(TreeNode node) {
  return lockedDescendantCount.get(node) > 0;
}

Why this works: Maintain a count of locked descendants for each node. Update counts during lock/unlock operations. Avoid O(n) DFS on every query.

boolean lock(TreeNode node, int userId) {
  if (node.isLocked) return false;
  if (hasLockedAncestor(node)) return false;
  if (hasLockedDescendant(node)) return false;
  
  node.isLocked = true;
  node.lockedBy = userId;
  updateAncestorCounts(node, +1); // increment locked count in ancestors
  return true;
}

Why this works: Check ancestors and descendants. If clear, lock the node and update ancestor counts.