C# Traverse tree and find all unique hierarchy chains from root to leaf

Question

I am working on a tree problem and not able to figure out how to solve the problem at hand. I've googled and also checked on SO, but could not find a suitable approach, so seeking help from the expert community.

Problem is this:

There is a class 'Person', defined like below. The class traces the hierarchy of a given Person.

public class Person
{
    public string Name { get; set; }
    public List<Person> Children { get; set; }
}

Now the hierarchy of a Person 'A' is defined like this:

Person A = new Person()
{
    Name = "A",
    Children = new List<Person>()
    {
        new Person()
        {
            Name = "B",
            Children = new List<Person>()
            {
                new Person()
                {
                    Name = "E",
                    Children = null
                },
                new Person()
                {
                    Name = "F",
                    Children = new List<Person>()
                    {
                        new Person()
                        {
                            Name = "H",
                            Children = null
                        }
                    }
                }
            }
        },

        new Person()
        {
            Name = "C",
            Children = new List<Person>()
            {
                new Person()
                {
                    Name = "G",
                    Children = null
                }
            }
        },

        new Person()
        {
            Name = "D",
            Children = null
        }
    }
};

So Person 'A' has 3 children (B,C,D).
'B' has 2 children (E,F),
'F' has 1 child (H),
'C' has 1 child (G),
'D' has no child.

And this class can model any person anywhere.
Now given another class where a given person can have only one child, like so:

public class PersonWithOneChildMax
{
    public string Name { get; set; }
    public PersonWithOneChildMax Child { get; set; }
}

How can I get hierarchy chains for Person 'A' earlier in terms of objects of 'PersonWithOneChildMax'?
So final result will be a list of 'PersonWithOneChildMax' and will contain 4 objects for the example above. Those 4 objects will be:

PersonWithOneChildMax firstChain = new PersonWithOneChildMax()
{
    Name = "A",
    Child = new PersonWithOneChildMax()
    {
        Name = "B",
        Child = new PersonWithOneChildMax()
        {
            Name = "E",
            Child = null
        }
    }
};

PersonWithOneChildMax secondChain = new PersonWithOneChildMax()
{
    Name = "A",
    Child = new PersonWithOneChildMax()
    {
        Name = "B",
        Child = new PersonWithOneChildMax()
        {
            Name = "F",
            Child = new PersonWithOneChildMax()
            {
                Name = "H",
                Child = null
            }
        }
    }
};

PersonWithOneChildMax thirdChain = new PersonWithOneChildMax()
{
    Name = "A",
    Child = new PersonWithOneChildMax()
    {
        Name = "C",
        Child = new PersonWithOneChildMax()
        {
            Name = "G",
            Child = null
        }
    }
};

PersonWithOneChildMax fourthChain = new PersonWithOneChildMax()
{
    Name = "A",
    Child = new PersonWithOneChildMax()
    {
        Name = "D",
        Child = null
    }
};

So in short, I am looking for a way to get all possible hierarchies for Person A:

A->B->E  
A->B->F->H  
A->C->G  
A->D 

How can I get the final result which will be a list of objects of type 'PersonWithOneChildMax' and will contain 4 objects defined above- 'firstChain', 'secondChain', 'thirdChain' and 'fourthChain' ?

Apologies for the very long question.

Answer 1

So walk the tree in depth-first order, keeping a list of the nodes you've visited along the way. Whenever you reach a leaf node (a person with no children), create a hierarchy and add it to the result list.

I haven't tested this, but the basic idea is:

public List<PersonWithOneChildMax> BuildFromPersonList(List<Person> people)
{
    var ancestors = new List<Person>();
    var result = new List<PersonWithOneChildMax>();
    foreach (var person in people)
    {
        BuildDescendants(person, ancestors, result);
    }
    return result;
}

private void BuildDescendants(Person person, List<Person> ancestors, List<PersonWithOneChildMax> result)
{
    if (person.Children == null || person.Children.Count == 0)
    {
        var newPerson = new PersonWithOneChildMax {Name = person.Name, Child = null};
        // build the hierarchy backwards
        for (var i = ancestors.Count - 1; i >= 0; --i)
        {
            newPerson = new PersonWithOneChildMax {Name = ancestors[i].Name, Child = newPerson};
        }
        result.Add(newPerson);
    }
    else
    {
        ancestors.Add(person);
        foreach (var child in person.Children)
        {
            BuildDescendants(child, ancestors, result);
        }
        ancestors.RemoveAt(ancestors.Count-1);
    }
}