Operations on Tree

Operations on Tree

What is this problem about?

The Operations on Tree problem asks you to design a data structure for a tree that supports: locking a node (if the node and all its descendants/ancestors are unlocked), unlocking a node, and upgrading a node (lock the node, unlock all its locked descendants). This design problem requires efficient tree traversal with lock state tracking.

Why is this asked in interviews?

Juspay and Google ask this because it tests tree design with parent tracking. The lock and upgrade operations require checking ancestors (all unlocked) and checking descendants (none locked, or for upgrade: at least one locked descendant). The array, BFS, hash table, design, DFS, and tree interview pattern is comprehensively exercised.

Algorithmic pattern used

Parent array + lock set + DFS for descendants. Store parent of each node. Maintain a set of locked nodes. lock(node, user): check no ancestor is locked (walk up parent chain) and node itself is unlocked. unlock(node, user): check node is locked by user. upgrade(node, user): check node is unlocked, at least one descendant is locked, no ancestor is locked. Then lock node and unlock all locked descendants (DFS/BFS to collect and clear them).

Example explanation

Tree: 0→(1,2)→(3,4) (0 is root). Lock(3,1): no ancestors locked, 3 unlocked → lock. Lock(2,1): no ancestors locked → lock. Upgrade(0,1): 0 unlocked, has locked descendants (2,3), no ancestor → lock 0, unlock 2 and 3. State: {0 locked}.

Common mistakes candidates make

• Not checking the user constraint (only the locking user can unlock).
• Incorrect ancestor check (must check ALL ancestors, not just parent).
• DFS for descendants during upgrade is O(n) — acceptable for the given constraints.
• Not atomically performing upgrade (check all conditions first, then execute).

Interview preparation tip

Tree design problems require careful state management. Separate the "check" phase from the "execute" phase in multi-step operations — this prevents partial state changes on failure. Storing the parent pointer for each node enables O(depth) ancestor checking. Practice lock/unlock tree designs — they appear in OS file-system locking, database record locking, and version control tree problems.