CODEWITHSUNDEEP
c#.netrecursiontree
user2990524
user2990524

Reputation: 13

Building a tree from a list using recursion

I've done a lot of searching, but none of the existing solutions solve my exact problem. I have a list:

Input[] inputs = new Input[]
{
    new Input(1),
    new Input(3,1),
    new Input(19,3),
    new Input(22,1),
    new Input(4,1),
    new Input(5,22),
};

Here is the declaration for BuildTree() which currently does not work:

public TreeNode BuildTree(IEnumerable<Input> inputs, TreeNode parentNode = null)
{
    List<Input> nodes = inputs.ToList<Input>();

    foreach (Input node in nodes)
    {
        TreeNode newNode = new TreeNode(node.Id);
        if (parentNode == null)
        {
            parentNode = BuildTree(nodes, newNode);
        }
        else
        {
            parentNode.AddChild(newNode);
        }
    }

    return parentNode;
}

Here is the call to BuildTree:

TreeNode rootNode = BuildTree(inputs);

So the BuildTree function has to return the root of the tree after building it. I've tried looping through the inputs. I've tried removing the first input from the list with each iteration. I can't quite figure it out. Any help would be greatly appreciated! Thank you!

Upvotes: 1

Views: 2530

Answers (1)

Gildor
Gildor

Reputation: 2574

You don't need recursion because you are transforming a list into a tree, not a tree into a list.

Since your input list is none of the standard tree traversals, and you did not tell us if parent nodes always come before child nodes, the easiest way we can use is a Dictionary.

public TreeNode BuildTree(IEnumerable<Input> inputs)
{
    TreeNode rootNode = null;
    // Build a dictionary to store each input and its node
    var dict = inputs.ToDictionary(
        input => input.Id,
        input => new { Input = input, Node = new TreeNode(input.Id.ToString()) });

    // Iterate through the nodes and build relationship among them
    foreach(var value in dict.Values)
    {
        var input = value.Input;
        if(input.ParentId != null)
        {
            dict[(int)input.ParentId].Node.Nodes.Add(value.Node);
        }
        else
        {
            rootNode = value.Node;
        }
    }
    return rootNode;
}

Upvotes: 1

Related Questions