How to flatten tree

Question

I have a nested list that contains

public class Person
{
    public Person(string name)
    {
        this.Name = name;
    }

    public string Name { get; set; }

    public List<Person> Childs { get; set; }
}

The list can be used like:

var Persons = new List<Person>();
Persons.Add(new Person("Eric"));
Persons[0].Childs = new List<Person>();
Persons[0].Childs.Add(new Person("Tom"));
Persons[0].Childs.Add(new Person("John"));
Persons[0].Childs[0].Childs = new List<Person>();
Persons[0].Childs[0].Childs.Add(new Person("Bill"));
Persons.Add(new Person("John");

How can I flatten this tree (put all nodes and sub-nodes, and sub-sub-nodes in a List), e.g. I want to display all children and parents on the same level, with a level Parameter. That means:

Before:

-Eric
    -Tom
    -John
        -Bill

What I want:

-Eric, Level1
-Tom, Level2
-John, Level2
-Bill, Level3

Why didn't nested for loops work for you? also you might want to look at recursion, however my thinking for you is to keep it simple for now, and just bang away at some for loops — TheGeneral, Mar 06 '19 at 09:21

fubo · Accepted Answer · 2019-03-06T09:37:31.683

6

Perfect use case for a recursive method

public static void DisplayPerson(List<Person> persons, int level = 0)
{
    if (persons != null)
    {
        level++;
        foreach (Person item in persons)
        {
            Console.WriteLine("-" + item.Name + ", Level" + level); 
            DisplayPerson(item.Childs, level);
        }
    }
}

https://dotnetfiddle.net/2J9F5K

edited Mar 06 '19 at 09:37

answered Mar 06 '19 at 09:28

fubo

44,811
17
103
137

1

Using recursive methods in cases like this [can cause overflows](https://stackoverflow.com/questions/491376/why-doesnt-net-c-optimize-for-tail-call-recursion/23349238). Use [`Stack`](https://stackoverflow.com/a/55020774/1275774) instead for these cases. – Mikael Dúi Bolinder Jun 14 '19 at 11:35

Mikael Dúi Bolinder · Answer 2 · 2022-12-05T00:27:50.513

Perfect use case for the Stack class.

public static void DisplayPerson(List<Person> persons)
{
    if (persons != null)
    {
        Stack<Person> personStack = new Stack<Person>();
        int level = 1;
        persons.ForEach(personStack.Push);
        while (personStack.Count > 0)
        {
            Person item = personStack.Pop();
            Console.WriteLine("-" + item.Name + ", Level:" + level); 
            if (item.Childs != null)
            {
                item.Childs.ForEach(personStack.Push);
                level++;
            }
        }
    }
}

https://dotnetfiddle.net/eD2GmY

Stack is way faster than a recursive method in C# and consumes way less memory, and you can avoid StackOverflows that sometimes are caused by recursive C# methods used like in @fubo's answer.

Recursive methods are only supposed to recurse once or twice. For use cases like this, with maybe thousands of items, you should use Stack instead.

score 0 · Answer 3 · answered Jan 27 '20 at 09:06

Very short code to flatten a tree without changing the original model:

  static void Main(string[] args)
{
    var flattedTree=new List<Person>();
    var Persons = new List<Person>();
    Persons.Add(new Person("Eric"));
    Persons[0].Childs = new List<Person>();
    Persons[0].Childs.Add(new Person("Tom"));
    Persons[0].Childs.Add(new Person("John"));
    Persons[0].Childs[0].Childs = new List<Person>();
    Persons[0].Childs[0].Childs.Add(new Person("Bill"));
    Persons.Add(new Person("John"));
    Flatten(Persons, flattedTree);
    //flattedTree variable is the flatted model of tree.
}
 static void Flatten(List<Person> nodes, List<Person> flattedNodes)
        {
            foreach (var node in nodes)
            {
                flattedNodes.Add(node);
                if (node.Childs?.Count > 0)
                    Flatten(node.Childs, flattedNodes);
            }
        }

How to flatten tree

3 Answers3