Building a tree from a list using recursion

Question

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!

so, it's a multileved tree, and what exactly is your problem (or what's not working?) — Noctis
– Noctis, Commented Nov 14, 2013 at 5:07

Gildor · Accepted Answer · 2013-11-14 06:09:52Z

1

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

answered Nov 14, 2013 at 6:09

Gildor

2,57424 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user2990524 Over a year ago

My apologies, I should have stated that the inputs are always sorted so that no element references a parent id that did not previously existed in the collection. The solution works great. Thank you!

Gildor Over a year ago

@user2990524 It's okay. Actually I would still suggest using a Dictionary since it's much easy to understand. The only difference is that you can remove the assignment of rootNode in the loop because you know it will come first.

Collectives™ on Stack Overflow

Building a tree from a list using recursion

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related