How to check if a node belongs to another node in a tree-CodePudding

I have a tree of users and I need to check if an user is below another specific user. In example: check if user7 is below user1 somewhere in the tree so user1 can see and manage the data of user7 (see the image I've attached).In this case it should be true What will be the best/ a good approach to do this?

Edit: I don't think just traveling the tree until it find the ancestor will work because if the users are in a database it will need multiple relational queries and won't be scalable

Edit: What I trying to achieve is an app where an user can manage the users that the user registers and those that the latter registers as well, and so on. Like in the image, user admin can manage all, user 1 can manage user 3,4 and 5 and all below them too. User4 can manage user6. User 1 can't manage user 2 neither user3 to user7

Edit: one approach I have figured is to create in a SQL database a user_administrators property in the users database table that have an array of user_id who can manage it and when they register an user just inherit all the users_id and add itself to it. But I don't know if there's a better way to do it or a more scalable way

CodePudding user response：

As you mention a dependency on a database, here is an example of what you could do on an SQL database that supports recursive queries, such as MySQL 8 :

Creation of the schema:

create table user (
    id int auto_increment primary key, 
    name varchar(100),
    manager_id int null
);
create index idx_user_name on user(name);

Populate with the example data given in the question:

insert into user(name) values("User Admin");
insert into user(name, manager_id)
    select name, (select id from user where name = "User Admin")
    from   (select "User 1" name union select "User 2") names;
insert into user(name, manager_id)
    select name, (select id from user where name = "User 1")
    from   (select "User 3" name union select "User 4" union select "User 5") names;
insert into user(name, manager_id)
    select "User 6", (select id from user where name = "User 2");
insert into user(name, manager_id)
    select "User 7", (select id from user where name = "User 4");

Now to know whether User 1 is in the manager line of User 7, perform this query:

with recursive cte as (
    select id, name, manager_id
    from user where name = "User 7"
    union all
    select user.id, user.name, user.manager_id 
    from cte inner join user on cte.manager_id = user.id
)
select 1 from cte where name = "User 1";

This query first locates the record for "User 7" and then walks up the tree collecting all persons on the manager line. Finally a simple select checks whether "User 1" occurs in this line.

If this query has a result record (the 1 is irrelevant), then the answer is "Yes". If the query returns no record, the answer is no.

If you can use the id fields instead of the name fields to identify users, that would be preferable as names could be non-unique.

CodePudding user response：

Ensure that for every node you can either navigate top-down or bottom up.

If top down, have a function that assembles the list of subnodes recursively, Once you have that, simply ask whether the node in question is amongst the subnodes of the reference node, or

If bottom-up, have a function that assembles the list of ancestors. Once you have that, simply ask wether the node in question is amongst the ancestors of the node in question.

Very likely the bottom-up approach is faster, regardless whether you have deep or wide trees.