# Permission Management for a General Tree

1\) Implement a TreeNode class that represents a general tree, i.e. one where each node can have an arbitrary number of children.

2\) Implement the following methods:

```
void grantAccess(TreeNode root);
void revokeAccess(TreeNode root);
boolean hasAccess(TreeNode root);
```

Once one grants access to a certain node, access is also granted to all of the nodes below that node too. The same logic follows for revokeAccess. Finally, hasAccess should be able to decide whether a hypothetical use has access to a certain node at a given time.

**Examples**

```
                    10
     1               2               3
  5    13       9    0    4          8

// ex 1
hasAccess(4); // false
revokeAccess(10);
hasAccess(4); // false 
grantAccess(2);
hasAccess(4); // true

// ex 2
hasAccess(4); // false
grantAccess(2);
hasAccess(4); // true
revokeAccess(10);
hasAccess(4); // false
```

**The Idea:** We need to define some kind of priority for when we want to conclude whether or not a node has access priveleges. One way to do this is to define use time element where the closest relevent time decides permission priveleges.

**Complexity:** O(1) time and space for both revokeAccess and grantAccess. O(N) worse case time where N is the number of nodes for hasAccess (consider the linkedlist n-ary tree). If the tree is fairly balanced: revokeAccess and grantAccess is the same, but now hasAccess is O(log\_k(N)) time (which is proportional to the number of levels in the tree).

```cpp
class TreeNode {
public:
    TreeNode(vector<TreeNode*> children, int id) : 
        id(id), children(children) {
        parent = nullptr;
    }

    TreeNode *parent;
    bool hasAccess = false;
    int time_element = 0;

private:
    const int id;
    vector<TreeNode*> children;
};


class PermissionManagement {
public:
    void grantAccess(TreeNode* root) {
        root->hasAccess = true;
        root->time_element = counter++;
    }

    void revokeAccess(TreeNode* root) {
        root->hasAccess = false;
        root->time_element = counter++;
    }

    bool hasAccess(TreeNode* root) {
        TreeNode *iter = root;
        vector<TreeNode*> time_elements;
        while (iter) {
            time_elements.push_back(iter);
            iter = iter->parent;
        }

        auto top_counter = *max_element(time_elements.begin(), time_elements.end(), 
            [] (const TreeNode* a, const TreeNode* b) {
            return a->time_element > b->time_element;
        });

        return top_counter->hasAccess;
    }

    static long long counter;
};

long long PermissionManagement::counter = 0;
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/design/permission-management-for-a-general-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.