CODEWITHSUNDEEP
c#listtree
Bob
Bob

Reputation: 191

How to flatten tree

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

Upvotes: 3

Views: 1929

Answers (3)

Mikael D&#250;i Bolinder
Mikael D&#250;i Bolinder

Reputation: 2287

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.

Upvotes: 2

Mohammad Niazmand
Mohammad Niazmand

Reputation: 1547

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);
            }
        }

Upvotes: 0

fubo
fubo

Reputation: 45947

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

Upvotes: 6

Related Questions