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).

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;