Convert Tree Structure to 2D Array

Question

I need to convert a tree-type structure into a 2D array.

I have a person class:

public class Person
{
    public string Name { get; set; }
    public List<Person> Children { get; } = new List<Person>();
}

Populated like this:

var parent = new Person {Name = "Parent"};
var child1 = new Person {Name = "Child 1"};
var grandchild1 = new Person {Name = "Grandchild 1"};
var child2 = new Person {Name = "Child 2"};

parent.Children.Add(child1);
child1.Children.Add(grandchild1);
parent.Children.Add(child2);

Eg:

| Parent |         |               |   
|        | Child 1 |               |
|        |         |  Grandchild 1 |
|        | Child 2 |               |

I want to convert it to the following array:

var expectedArray = new object[,]
{
    {"Parent", null, null},
    {null, "Child 1", null},
    {null, null, "Grandchild 1"},
    {null, "Child 2", null}
};

At the moment I've written a couple of extension methods but it's really messy. What's the correct way to do this? Preferably in a short contained method.

This is what I havae tried so far, but it's really messy.

public static class PersonExtensions
{
    public static object[,] To2DArray(this Person person)
    {
        var rowIndex = 0;
        var columnIndex = 0;

        var objectArray = new object[person.GetTotalPersonCount(), person.GetMaxDepth()];

        var stack = new Stack<List<Person>.Enumerator>();
        var enumerator = (new List<Person> {person}).GetEnumerator();
        enumerator.MoveNext();

        do
        {
            var currentPerson = enumerator.Current;
            objectArray[rowIndex, columnIndex] = currentPerson.Name;

            rowIndex++;
            if (currentPerson.Children.Any())
            {
                // Depth is increasing
                columnIndex++;
                stack.Push(enumerator);
                enumerator = currentPerson.Children.GetEnumerator();
            }

            // if (!enumerator.MoveNext() && stack.Count > 0)
            while (!enumerator.MoveNext() && stack.Count > 0)
            {
                // Depth is decreasing
                enumerator = stack.Pop();
                columnIndex--;
            }
        }
        while (stack.Count > 0);

        return objectArray;
    }

    public static int GetMaxDepth(this Person entity)
    {
        int maxDepth = 0;

        foreach (var childEntity in entity.Children)
        {
            maxDepth = Math.Max(maxDepth, childEntity.GetMaxDepth());
        }

        return maxDepth + 1;
    }

    public static int GetTotalPersonCount(this Person entity)
    {
        int count = 1;

        foreach (var childEntity in entity.Children)
        {
            count += childEntity.GetTotalPersonCount();
        }

        return count;
    }
}

Edit I have managed to get it working by replacing the final if (depth descreasing) with a while. It still looks overly complicated though.

Answer 1

Here's how it should work as a single loop (untested!):

       for (; ; )
            if (!enumerator.MoveNext())
            {
                if (stack.Count == 0)
                    break; // finished
                           // Depth is decreasing
                enumerator = stack.Pop();
                columnIndex--;
            }
            else
            {
                var currentPerson = enumerator.Current;
                objectArray[rowIndex, columnIndex] = currentPerson.Name;

                rowIndex++;

                if (currentPerson.Children.Any())
                {
                    // Depth is increasing
                    columnIndex++;
                    stack.Push(enumerator);
                    enumerator = currentPerson.Children.GetEnumerator();
                }
            }

If you wanted it to look a little cleaner you could do something like:

 Func<bool> getNext = () => 
 { 
     if (!enumerator.MoveNext()) 
     { 
         if (stack.Count == 0) return false; 
         enumerator = stack.Pop(); columnIndex--; 
     } 
     return true; 
 };

 while (getNext())
 {
     var currentPerson = enumerator.Current;
     //etc.
 }

Answer 2

I believe the problem can be solved by using depth-first search in two passes. First, the height of the tree has to be determined in the first pass. The depth needs to be known in order to know how many entries will be in every line of the result.

Next, in a second pass, the actual entries have to be generated, assigning the node's name to the entry corresponding to its depth in the tree.

The first step can be done as follows by implementing it as an extension method of the Person class using Linq.

public static int Depth(this Person iPerson)
{
    if (iPerson.Children == null || iPerson.Children.Count() == 0)
    {
        return 1;
    }
    else
    {
        return 1 + Children.Max( iChild => iChild.Depth() );
    }
}

The second step can be implemented as follows, where iRoot is the root of the tree.

public static void DepthFirst(int Depth,
                              int CurrentDepth,
                              Person iRoot,
                              List<string>[] Result)
{
    string[] NewEntry = new string[Depth];
    NewEntry[CurrentDepth] = iPerson.Name;
    Result.Add(NewEntry);
    foreach(var iChild in iPerson.Children)
    {
        DepthFirst(Depth, CurrentDepth + 1, iChild, Result);
    }
}

int Depth = iRoot.Depth();
var Result = new List<string[]>();
DepthFirst(Depth, 0, iRoot, Result).