Operations on Tree

Medium · Graphs · Explanation and code example

Iterative DFS

How it works

This approach converts the recursive dfs into an iterative version using an explicit stack. This is useful when you want to avoid recursion overhead or potential stack overflow on very large trees, while maintaining the depth-first traversal order.

The core logic for all three operations remains unchanged from the recursive dfs solution.

Steps

  1. Initialization: Build child adjacency lists and initialize the locked array.
  2. lock and unlock: Same O(1) checks.
  3. upgrade(num, user):
    • Traverse ancestors to ensure none are locked.
    • Use a stack to perform iterative dfs on descendants.
    • Pop nodes, check if locked, unlock if so, and push children.
    • If any descendants were locked, lock num and return true.

Complexity

  • Time complexity:
    • O(n) time for initialization.
    • O(1) time for each lock() and unlock() function call.
    • O(n) time for each upgrade() function call.
  • Space complexity: O(n)

Things to watch for

Not Checking All Ancestors for Upgrade

The upgrade operation requires that no ancestor of the node is locked. Checking only the immediate parent is insufficient. You must traverse the entire path from the node to the root, verifying each ancestor is unlocked before proceeding.

Forgetting to Unlock Descendants Before Locking

When upgrade succeeds, all locked descendants must be unlocked before locking the current node. Some solutions lock the node first, which means when traversing descendants, the node itself gets incorrectly counted or unlocked. Process descendants completely before modifying the current node.

Returning True When No Descendants Are Locked

The upgrade operation requires at least one locked descendant. Even if all other conditions are met (node unlocked, ancestors unlocked), if no descendant is locked, the operation must return false. Always verify the locked descendant count is greater than zero before returning success.

Python code example

from typing import List

class LockingTree:

    def __init__(self, parent: List[int]):
        self.parent = parent
        self.child = [[] for _ in range(len(parent))]
        self.locked = [0] * len(parent)
        for node in range(1, len(parent)):
            self.child[parent[node]].append(node)

    def lock(self, num: int, user: int) -> bool:
        if self.locked[num]:
            return False
        self.locked[num] = user
        return True

    def unlock(self, num: int, user: int) -> bool:
        if self.locked[num] != user:
            return False
        self.locked[num] = 0
        return True

    def upgrade(self, num: int, user: int) -> bool:
        node = num
        while node != -1:
            if self.locked[node]:
                return False
            node = self.parent[node]

        lockedCount, stack = 0, [num]
        while stack:
            node = stack.pop()
            if self.locked[node]:
                self.locked[node] = 0
                lockedCount += 1
            stack.extend(self.child[node])

        if lockedCount:
            self.locked[num] = user
            return True
        return False

C++ code example

class LockingTree {
private:
    vector<int> parent;
    vector<vector<int>> child;
    vector<int> locked;

public:
    LockingTree(vector<int>& parent) : parent(parent), locked(parent.size()) {
        int n = parent.size();
        child.resize(n);
        for (int node = 1; node < n; node++) {
            child[parent[node]].push_back(node);
        }
    }

    bool lock(int num, int user) {
        if (locked[num]) {
            return false;
        }
        locked[num] = user;
        return true;
    }

    bool unlock(int num, int user) {
        if (locked[num] != user) {
            return false;
        }
        locked[num] = 0;
        return true;
    }

    bool upgrade(int num, int user) {
        int node = num;
        while (node != -1) {
            if (locked[node]) {
                return false;
            }
            node = parent[node];
        }

        int lockedCount = 0;
        stack<int> stk;
        stk.push(num);

        while (!stk.empty()) {
            node = stk.top(); stk.pop();
            if (locked[node]) {
                locked[node] = 0;
                lockedCount++;
            }
            for (int& nei : child[node]) {
                stk.push(nei);
            }
        }

        if (lockedCount > 0) {
            locked[num] = user;
            return true;
        }
        return false;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations