CODEWITHSUNDEEP
c#algorithm
Ivan-Mark Debono
Ivan-Mark Debono

Reputation: 16320

Is it possible to build a tree from a list?

I have this data structure:

public class Node
{
    public String Name {get; set;}
    public List<Link> Links {get; set;} 
}

public class Link
{
    public int Id {get; set;}
}

The data might consist of:

Node    Links
--------------------
A       1
B       2, 3
C       4, 5
D       6

A is the start node and D is the end node. The nodes in-between are in a fixed order. The result should be a list of 'paths' from A to D which will be:

A1->B2->C4->D6
A1->B2->C5->D6
A1->B3->C4->D6
A1->B3->C5->D6

Which algorithm can be used to get to the above result?

Upvotes: 1

Views: 158

Answers (1)

Jens R.
Jens R.

Reputation: 191

Have a look at this recursive implementation:

using System;

public class Node {
    public String Name {get; set;}
    public int[] Links {get; set;} 
}

public class Program
{
    private static Node[] nodes = new[] {
        new Node { Name = "A", Links = new[] { 1 } },
        new Node { Name = "B", Links = new[] { 2, 3 } },
        new Node { Name = "C", Links = new[] { 4, 5 } },
        new Node { Name = "D", Links = new[] { 6 } }
    };

    private static void PrintPath(int depth, string path)
    {
        if (depth == nodes.Length) 
        {
            Console.WriteLine(path);
        }
        else 
        {
            foreach(var link in nodes[depth].Links)
            {
                PrintPath(
                    depth+1, 
                    string.Format("{0}{1}{2} ", path, nodes[depth].Name, link));
            }
        }
    }

    public static void Main()
    {
        PrintPath(0, string.Empty);
    }
}

For the sake of simplicity, I've replaced the Link class with int and used arrays instead of lists, but you should get the idea.

Upvotes: 2

Related Questions