How to check if is descendant within tree structure?

I have following structure:

 class Employee
        {
            public long Id { get; set; }

            public long? ParentId { get; set; }

            public Employee(long id, long? parentId)
            {
                Id = id;
                Parent_Id = parentId;
            }
        }

Let's build some tree structure:

        var employees = new List<Employee>();

        employees.Add(new Employee(1 , null));
        employees.Add(new Employee(2 , 1));
        empl开发者_开发知识库oyees.Add(new Employee(3 , 2));

How to check (using C#) if employee with Id=1 is parent of employee with Id=3 within this list? Tree structure could be much more complicated .

---

To check if is descendant you can traverse up the tree and see if you find him:

static bool GetIsDescendant(long idChild, long idAncestor, IEnumerable<Employee> employees)
{
    return GetAncestors(idChild, employees).Any(t => t.Id == idAncestor);
}

static IEnumerable<Employee> GetAncestors(long idEmployee, IEnumerable<Employee> employees)
{
    var employee = employees.SingleOrDefault(e => e.Id == idEmployee);

    if (employee == null)
    {
        yield break;
    }

    while (employee.ParentId.HasValue)
    {
        var parent = employees.SingleOrDefault(e => e.Id == employee.ParentId.Value);

        if (parent == null)
        {
            yield break;
        }
        else
        {
            employee = parent;
            yield return parent;
        }
    }
}

---

You could do it like this:

static bool IsParent(
    IEnumerable<Employee> employees, long potentialParentId, long potentialChildId)
{
    var potentialChild = employees.SingleOrDefault(e => e.Id == potentialChildId);
    return potentialChild != null && potentialChild.ParentId == potentialParentId;
}

But doing this could be very slow, especially if you had many employees. If you want to make the lookup by Id fast, you can use Dictionary<long, Employee>.

---

When dealing with trees in the object model, I find it more useful if the object has Children. Although it is easier still to maintain the Parent as you are doing. In fact, you can abstract the tree into a generic interface, or two:

public interface IHaveChildren<out T> where T:IHaveChildren<T>
{
    /// <summary>Gets the children.</summary>
    IEnumerable<T> Children { get; }
}

public interface IHaveFamily<out T> : IHaveChildren<T> where T : IHaveChildren<T>
{
    /// <summary>Gets the Parent.</summary>
    T Parent { get; }
}

Now you can set up lots of interesting and useful extensions to get tree info without making your poor Employee class have to worry about that too! Here are two such extensions that take advantage of these interfaces.

public static class HeirarchyExtensions
{

    public static bool IsAncestorOf<T>(this IHaveFamily<T> instance1, IHaveFamily<T> instance2) where T : IHaveFamily<T>
    {
        if(instance1.IsLeaf()) return false;

        foreach (var child in instance1.Children)
        {
            if (child.Equals(instance2)) return true;
            return instance1.IsAncestorOf(child);
        }
        return false;
    }

    public static IEnumerable<T> GetDescendents<T>(this IHaveFamily<T> instance) where T : IHaveFamily<T>
    {
        var result = instance.Children;
        if(!result.Any()) 
            return result;
        foreach (var child in instance.Children) {
            result = result.Concat(child.Children);
        }
        return result;
    }

}

HTH,
Berryl