What would be an appropriate data structure for this problem?

1

Hi, I want to maintain a hierarchical organization of employees in a company. Each employee has an ID and a level which refers to where the person stands in the hierarchy. And I want my tree-based data structure to facilitate the following operations.
add(a,b) → this function adds a new node with id a to the node with id b
del(a,b) → removes a from the tree and adds all of its children to b
lca(a,b) → returns lowest common ancestor of node a and b

Now the question is, what is the best data structure to use so as to handle multiple queries in logN time?
NOTE: The tree is not binary.

2

Do you mean company is a graph with employees as nodes with node values as ID and each node has some level in graph …?

Finding LCA in log(n) is feasible if you are not distorting the graph… but as you mentioned of Add & delete type query that changes the nodes present in graph which means Edges changes hence the graph.

I don’t think that there is any way to get LCA in log(n) for such operation but if there is please let me know too!! :face_with_monocle:

3

Yes it is a graph but strictly speaking it will be a tree as you would never want to work under your junior :sweat_smile: .
I don’t know how can we handle the add query in logN time I mean it would anyway take me linear time to find the node with id b and then add an edge.

4

Can we use DSU here?

5

NO, it won’t work here