What is the time complexity of Operations on Tree?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Operations on Tree?

This problem uses Array, Hash Table, Tree, Depth-First Search, Breadth-First Search, Design. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Operations on Tree?

Insight 1: Representing the tree using adjacency lists (children) is efficient for finding descendants in the upgrade operation. Insight 2: Maintaining a 'locked' array to track the user who locked a node allows for constant-time lock/unlock checks.

Which companies ask LeetCode 1993. Operations on Tree in interviews?

This problem is frequently asked at Juspay.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Operations on Tree - LeetCode 1993 Solution

Operations on Tree - Complete Solution Guide

Operations on Tree is LeetCode problem 1993, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 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 n

Detailed Explanation

The problem requires you to design a data structure, `LockingTree`, representing a tree with lock/unlock capabilities for individual nodes by different users. The tree is provided as a parent array, where `parent[i]` is the parent of node `i`, and node 0 is the root (parent[0] = -1). The data structure must support three operations: `lock(num, user)`, `unlock(num, user)`, and `upgrade(num, user)`. The `lock` operation allows a user to lock an unlocked node. The `unlock` operation allows a user to unlock a node they have previously locked. The `upgrade` operation is more complex: it locks a node for a given user, but only if the node is currently unlocked, it has at least one locked descendant (locked by any user), and none of its ancestors are locked. If the upgrade is successful, it also unlocks all the descendants of the upgraded node, regardless of who locked them.

Solution Approach

The solution implements the `LockingTree` class with the required methods. It uses an array `parent` to store the parent-child relationship, an array `locked` to store the user who has locked each node (0 if unlocked), and an adjacency list `children` to easily find the children of each node. `lock` and `unlock` simply check and update the `locked` array. The `upgrade` method first checks if the node is unlocked and if none of its ancestors are locked. Then, it uses Breadth-First Search (BFS) to determine if the node has any locked descendants. If all conditions are met, it locks the node, and then uses BFS again to unlock all its descendants.

Step-by-Step Algorithm

Step 1: **Initialization (`__init__` / Constructor):** Store the `parent` array, initialize the `locked` array to 0 (unlocked), and create the `children` adjacency list to represent the tree's structure. Traverse parent array and for each node `i` that is not the root, add `i` to the children of parent[i].
Step 2: **Lock (`lock`):** Check if the node `num` is currently unlocked (`locked[num] == 0`). If it is, lock it by setting `locked[num] = user` and return `True`. Otherwise, return `False`.
Step 3: **Unlock (`unlock`):** Check if the node `num` is locked by the given user (`locked[num] == user`). If it is, unlock it by setting `locked[num] = 0` and return `True`. Otherwise, return `False`.
Step 4: **Upgrade (`upgrade`):** a. Check if the node `num` is locked; if so, return `False`. b. Check if any ancestor of node `num` is locked; if so, return `False`. Traverse upwards from `num` to the root by following parent links. Return false if any ancestor is locked. c. Check if node `num` has at least one locked descendant. BFS is used to traverse descendants. Return false if no locked descendant found. d. If all the above conditions are met, lock node `num` for the given user, and unlock all descendants of node `num`. Another BFS is used. e. Return `True` if upgrade was successful.

Key Insights

Insight 1: Representing the tree using adjacency lists (children) is efficient for finding descendants in the upgrade operation.
Insight 2: Maintaining a 'locked' array to track the user who locked a node allows for constant-time lock/unlock checks.
Insight 3: The upgrade operation's constraints require carefully checking ancestors and descendants, so a clean implementation is vital to avoid errors.
Insight 4: Using BFS to traverse descendants for both checking for locked nodes during `upgrade` and unlocking them after upgrading is efficient.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Tree, Depth-First Search, Breadth-First Search, Design.

Companies

Asked at: Juspay.

Operations on Tree | LeetCode 1993

Medium

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

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class LockingTree {

    private int[] parent;
    private int n;
    private int[] locked;
    private List<List<Integer>> children;

    public LockingTree(int[] parent) {
        this.parent = parent;
        this.n = parent.length;
        this.locked = new int[n];
        this.children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            this.children.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            int p = parent[i];
            if (p != -1) {
                this.children.get(p).add(i);
            }
        }
    }

    public boolean lock(int num, int user) {
        if (this.locked[num] == 0) {
            this.locked[num] = user;
            return true;
        }
        return false;
    }

    public boolean unlock(int num, int user) {
        if (this.locked[num] == user) {
            this.locked[num] = 0;
            return true;
        }
        return false;
    }

    public boolean upgrade(int num, int user) {
        if (this.locked[num] != 0) {
            return false;
        }

        int curr = this.parent[num];
        while (curr != -1) {
            if (this.locked[curr] != 0) {
                return false;
            }
            curr = this.parent[curr];
        }

        Queue<Integer> q_check = new LinkedList<>(this.children.get(num));
        boolean has_locked_descendant = false;
        while (!q_check.isEmpty()) {
            int node = q_check.poll();
            if (this.locked[node] != 0) {
                has_locked_descendant = true;
                break;
            }
            for (int child : this.children.get(node)) {
                q_check.add(child);
            }
        }

        if (!has_locked_descendant) {
            return false;
        }

        this.locked[num] = user;
        Queue<Integer> q_unlock = new LinkedList<>(this.children.get(num));
        while (!q_unlock.isEmpty()) {
            int node = q_unlock.poll();
            this.locked[node] = 0;
            for (int child : this.children.get(node)) {
                q_unlock.add(child);
            }
        }

        return true;
    }
}

/**
 * Your LockingTree object will be instantiated and called as such:
 * LockingTree obj = new LockingTree(parent);
 * boolean param_1 = obj.lock(num,user);
 * boolean param_2 = obj.unlock(num,user);
 * boolean param_3 = obj.upgrade(num,user);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1993: Operations on Tree - Detailed explanation and solution approaches.

Topics

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

Companies

Juspay

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1993

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: **Initialization (`__init__` / Constructor):** Store the `parent` array, initialize the `locked` array to 0 (unlocked), and create the `children` adjacency list to represent the tree's structure. Traverse parent array and for each node `i` that is not the root, add `i` to the children of parent[i].
2
Step 2: **Lock (`lock`):** Check if the node `num` is currently unlocked (`locked[num] == 0`). If it is, lock it by setting `locked[num] = user` and return `True`. Otherwise, return `False`.
3
Step 3: **Unlock (`unlock`):** Check if the node `num` is locked by the given user (`locked[num] == user`). If it is, unlock it by setting `locked[num] = 0` and return `True`. Otherwise, return `False`.
4
Step 4: **Upgrade (`upgrade`):** a. Check if the node `num` is locked; if so, return `False`. b. Check if any ancestor of node `num` is locked; if so, return `False`. Traverse upwards from `num` to the root by following parent links. Return false if any ancestor is locked. c. Check if node `num` has at least one locked descendant. BFS is used to traverse descendants. Return false if no locked descendant found. d. If all the above conditions are met, lock node `num` for the given user, and unlock all descendants of node `num`. Another BFS is used. e. Return `True` if upgrade was successful.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The `lock` and `unlock` operations take O(1) time. The `upgrade` operation takes O(n) in the worst case because checking for locked ancestors could involve traversing up to the root. The descendant checks and unlocks in `upgrade` also use BFS, which can visit every node in the worst case. The space complexity is O(n) because the `children` adjacency list can store up to n-1 edges (each node can have at most n-1 children implicitly represented in children lists), and the `locked` and `parent` arrays both take O(n) space. The BFS queues use O(n) space in the worst case.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS) for descendant checks

Instead of BFS, DFS can be used to check for locked descendants and to unlock them. This might offer slightly different performance characteristics depending on the tree's structure.

Time: O(n)Space: O(n) in the worst case (skewed tree) due to recursion depth.

Trade-offs: DFS can be more space-efficient for balanced trees, but might have stack overflow issues or use more space than BFS for highly skewed trees. BFS is generally more predictable in terms of memory usage and avoids potential stack overflow issues.

✨

Key Insights

1Insight 1: Representing the tree using adjacency lists (children) is efficient for finding descendants in the upgrade operation.
2Insight 2: Maintaining a 'locked' array to track the user who locked a node allows for constant-time lock/unlock checks.
3Insight 3: The upgrade operation's constraints require carefully checking ancestors and descendants, so a clean implementation is vital to avoid errors.
4Insight 4: Using BFS to traverse descendants for both checking for locked nodes during `upgrade` and unlocking them after upgrading is efficient.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Node 0 (the root) being upgraded. The solution correctly handles this because the ancestor check will terminate immediately as parent[0] = -1.
Edge case 2: A node with no children being upgraded. The descendant check should return false if the node itself is not locked.
Edge case 3: Multiple locked descendants. The unlock operation in upgrade should unlock all of them.
Edge case 4: A node being upgraded that is an ancestor of another locked node. This should return false.
Edge case 5: Calling upgrade on a node that is already locked by some user. The solution should return false.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to check for locked ancestors in the `upgrade` operation.

✗Common mistake 2: Incorrectly implementing the descendant check, potentially missing locked descendants or including ancestors by mistake.

✗Common mistake 3: Failing to unlock all descendants during the `upgrade` operation. Make sure the unlocking process also unlocks the descendants of the descendants.

✗Common mistake 4: Assuming `num` must be in the range of node indices, when in fact the constraint is just that its at most n - 1. (Although this error wont arise for correctly formed input following the constraints, it's a good defensive programming practice)

✗Common mistake 5: Not considering the scenario where a node being upgraded might have a locked descendant and a locked ancestor. The solution MUST check for BOTH. First Ancestor, then Descendant.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Hierarchical resource locking in operating systems or distributed systems, where access to resources must be controlled and escalated or revoked based on privileges.

🏦Real-world scenario 2: Access control in organizational hierarchies, where users or groups can be granted permissions to access specific data or functionalities, and those permissions can be inherited or revoked based on their position in the hierarchy.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 14, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Operations on Tree"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?