A tricky one involving List<T> and object casting

Question

I was given this question at a job interview recently and couldn't figure out how to do it elegantly. Ever since, it has been nagging away at me and I can't work out if its a lack of knowledge about some 'modern' technique/technology I'm unaware of or if I'm just stupid. Any advice would be very welcome.

The Problem

Imagine a simple class hierarchy:

abstract class Person {
    public string Name { get; set; }
}

class Child : Person { }

class Parent : Person {
    public List<Person> Children { get; set; }
}

class Ancestor : Parent { }

The problem is how to traverse a hierarchy of such objects and to print out all the people encountered. So for the following scenario:

Ancestor myAncestor = new Ancestor {    
    Name = "GrandDad",
    Children = new List<Person> { 
        new Child { Name = "Aunt" },
        new Child { Name = "Uncle" },
        new Parent {
            Name = "Dad", 
            Children = new List<Person> { 
                new Child { Name = "Me" }, 
                new Child { Name = "Sister" } 
            }
        }
    }
};

the output should be something like:

GrandDad  
-    Aunt  
-    Uncle  
-    *Dad  
         -Me  
         -Sister

All the processing needs to be done within a single method that accepts a single parameter of type Ancestor.

I implemented, almost without thinking, a simple recursive solution but of course because of the way the objects involved relate to each other things aren't as simple as all that.

Try as I might I cannot think of a clean way of doing this and my post-interview Googlings have suggested I need to be doing something that is (to me, with only a working knowledge of LINQ and List<T>) something considerably more technically advanced than the sort of web-dev coding I've been doing for the last decade or so. Is this the case? Or should I be thinking of getting out of software development on the grounds that I'm rubbish at it?

Update

Thanks to you all for your responses/suggestions. I've accepted @Daniel Hilgarth's answer primarily because it was the only one I could genuinely understand :-o

Answer 1

I agree with Marc's comment saying that this type system is non-sense. Still, you can solve it with delegates. That's a bit of cheating, because basically they are nothing more than methods, but here we go:

void PrintFamily(Ancestor a)
{
    Action<Parent, int> printParent = null;
    printParent = (parent, level) => 
    {
        var indentation = new string(' ', level * 4);
        var indentationChildren = new string(' ', (level + 1) * 4);
        Console.WriteLine(indentation + parent.Name);
        foreach(var child in parent.Children)
        {
            if(child is Child)
                Console.WriteLine(indentationChildren + child.Name);
            else if(child is Parent)
            {
                printParent((Parent)child, level + 1);
            }
        }
    };

    printParent(a, 0);
}

Answer 2

This is horrible, but within the scope of the question (no extra methods, so can't add polymorphism/discriminator, and method must take Ancestor, so no method recursion):

static void Write(Ancestor root)
{
    // stack since depth-first
    var stack = new Stack<Tuple<Person,int>>();
    stack.Push(Tuple.Create((Person)root, 0));

    while(stack.Count > 0)
    {
        var pair= stack.Pop();
        var person = pair.Item1;

        // indentation
        Console.Write(new string('\t', pair.Item2));
        Parent parent = person as Parent;

        // node markers aren't fully specified, but this gets somewhere
        // near; maybe * should actually be checking Children != null &&
        // Children.Count > 0             
        if(person == root) {}
        else if (parent != null) { Console.Write("*");}
        else {Console.Write("-");}            

        Console.WriteLine(person.Name);

        // recursion on the stack
        if(parent != null && parent.Children != null) {
            foreach(var next in Enumerable.Reverse(parent.Children)) {
                stack.Push(Tuple.Create(next, pair.Item2 + 1));
            }
        }
    }
}

Answer 3

Here's my go, using a stack to emulate recursion:

static void PrintTree(Ancestor ancestor)
{
    Stack<Tuple<int, Person>> PersonStack = new Stack<Tuple<int, Person>>();
    PersonStack.Push(new Tuple<int, Person>(0, ancestor));

    while (PersonStack.Count != 0)
    {
        Tuple<int, Person> NextPerson = PersonStack.Pop();

        Console.WriteLine(new string(' ', NextPerson.Item1) + NextPerson.Item2.Name);

        Parent NextPersonAsParent = NextPerson.Item2 as Parent;
        if (NextPersonAsParent != null && NextPersonAsParent.Children != null)
        {
            foreach (var Child in NextPersonAsParent.Children)
            {
                PersonStack.Push(new Tuple<int, Person>(NextPerson.Item1 + 1, Child));
            }
        }
    }
}

Answer 4

internal void ToString(Ancestor root)
{
    Trace.WriteLine(root.Name);
    Trace.Indent();
    foreach(var child in root.Children)
    {
         if(child is Parent)
             ToString(new Ancestor(){Name = child.Name, 
                                     Children = ((Parent)child).Children});
         else
             Trace.WriteLine(child.Name);
    }
    Trace.Unindent();
}