Avatar of artemkorsakov

artemkorsakov's solution

to Tree Building in the C# Track

Published at May 02 2019 · 0 comments
Instructions
Test suite
Solution

Refactor a tree building algorithm.

Some web-forums have a tree layout, so posts are presented as a tree. However the posts are typically stored in a database as an unsorted set of records. Thus when presenting the posts to the user the tree structure has to be reconstructed.

Your job will be to refactor a working but slow and ugly piece of code that implements the tree building logic for highly abstracted records. The records only contain an ID number and a parent ID number. The ID number is always between 0 (inclusive) and the length of the record list (exclusive). All records have a parent ID lower than their own ID, except for the root record, which has a parent ID that's equal to its own ID.

An example tree:

root (ID: 0, parent ID: 0)
|-- child1 (ID: 1, parent ID: 0)
|    |-- grandchild1 (ID: 2, parent ID: 1)
|    +-- grandchild2 (ID: 4, parent ID: 1)
+-- child2 (ID: 3, parent ID: 0)
|    +-- grandchild3 (ID: 6, parent ID: 3)
+-- child3 (ID: 5, parent ID: 0)

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the Skip property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using exercism submit TreeBuilding.cs

Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

TreeBuildingTest.cs

using System;
using Xunit;

public class TreeBuildingTest
{
    [Fact]
    public void One_node()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 }
        };

        var tree = TreeBuilder.BuildTree(records);

        AssertTreeIsLeaf(tree, id: 0);
    }

    [Fact(Skip = "Remove to run test")]
    public void Three_nodes_in_order()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 2, ParentId = 0 }
        };

        var tree = TreeBuilder.BuildTree(records);

        AssertTreeIsBranch(tree, id: 0, childCount: 2);
        AssertTreeIsLeaf(tree.Children[0], id: 1);
        AssertTreeIsLeaf(tree.Children[1], id: 2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Three_nodes_in_reverse_order()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 2, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 }
        };

        var tree = TreeBuilder.BuildTree(records);

        AssertTreeIsBranch(tree, id: 0, childCount: 2);
        AssertTreeIsLeaf(tree.Children[0], id: 1);
        AssertTreeIsLeaf(tree.Children[1], id: 2);
    }

    [Fact(Skip = "Remove to run test")]
    public void More_than_two_children()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 3, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 2, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 }
        };

        var tree = TreeBuilder.BuildTree(records);

        AssertTreeIsBranch(tree, id: 0, childCount: 3);
        AssertTreeIsLeaf(tree.Children[0], id: 1);
        AssertTreeIsLeaf(tree.Children[1], id: 2);
        AssertTreeIsLeaf(tree.Children[2], id: 3);
    }

    [Fact(Skip = "Remove to run test")]
    public void Binary_tree()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 5, ParentId = 1 },
            new TreeBuildingRecord { RecordId = 3, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 2, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 4, ParentId = 1 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 6, ParentId = 2 }
        };

        var tree = TreeBuilder.BuildTree(records);

        AssertTreeIsBranch(tree, id: 0, childCount: 2);
        AssertTreeIsBranch(tree.Children[0], id: 1, childCount: 2);
        AssertTreeIsBranch(tree.Children[1], id: 2, childCount: 2);

        AssertTreeIsLeaf(tree.Children[0].Children[0], id: 4);
        AssertTreeIsLeaf(tree.Children[0].Children[1], id: 5);
        AssertTreeIsLeaf(tree.Children[1].Children[0], id: 3);
        AssertTreeIsLeaf(tree.Children[1].Children[1], id: 6);
    }

    [Fact(Skip = "Remove to run test")]
    public void Unbalanced_tree()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 5, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 3, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 2, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 4, ParentId = 1 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 6, ParentId = 2 }
        };

        var tree = TreeBuilder.BuildTree(records);

        AssertTreeIsBranch(tree, id: 0, childCount: 2);
        AssertTreeIsBranch(tree.Children[0], id: 1, childCount: 1);
        AssertTreeIsBranch(tree.Children[1], id: 2, childCount: 3);

        AssertTreeIsLeaf(tree.Children[0].Children[0], id: 4);
        AssertTreeIsLeaf(tree.Children[1].Children[0], id: 3);
        AssertTreeIsLeaf(tree.Children[1].Children[1], id: 5);
        AssertTreeIsLeaf(tree.Children[1].Children[2], id: 6);
    }

    [Fact(Skip = "Remove to run test")]
    public void Empty_input()
    {
        var records = new TreeBuildingRecord[0];

        Assert.Throws<ArgumentException>(() => TreeBuilder.BuildTree(records));
    }

    [Fact(Skip = "Remove to run test")]
    public void Root_node_has_parent()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 0, ParentId = 1 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 }
        };

        Assert.Throws<ArgumentException>(() => TreeBuilder.BuildTree(records));
    }

    [Fact(Skip = "Remove to run test")]
    public void No_root_node()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 }
        };

        Assert.Throws<ArgumentException>(() => TreeBuilder.BuildTree(records));
    }


    [Fact(Skip = "Remove to run test")]
    public void Non_continuous()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 2, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 4, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 }
        };

        Assert.Throws<ArgumentException>(() => TreeBuilder.BuildTree(records));
    }

    [Fact(Skip = "Remove to run test")]
    public void Cycle_directly()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 5, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 3, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 2, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 4, ParentId = 1 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 6, ParentId = 3 }
        };

        Assert.Throws<ArgumentException>(() => TreeBuilder.BuildTree(records));
    }

    [Fact(Skip = "Remove to run test")]
    public void Cycle_indirectly()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 5, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 3, ParentId = 2 },
            new TreeBuildingRecord { RecordId = 2, ParentId = 6 },
            new TreeBuildingRecord { RecordId = 4, ParentId = 1 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 6, ParentId = 3 }
        };

        Assert.Throws<ArgumentException>(() => TreeBuilder.BuildTree(records));
    }

    [Fact(Skip = "Remove to run test")]
    public void Higher_id_parent_of_lower_id()
    {
        var records = new[]
        {
            new TreeBuildingRecord { RecordId = 0, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 2, ParentId = 0 },
            new TreeBuildingRecord { RecordId = 1, ParentId = 2 }
        };

        Assert.Throws<ArgumentException>(() => TreeBuilder.BuildTree(records));
    }

    private static void AssertTreeIsBranch(Tree tree, int id, int childCount)
    {
        Assert.Equal(id, tree.Id);
        Assert.False(tree.IsLeaf);
        Assert.Equal(childCount, tree.Children.Count);
    }

    private static void AssertTreeIsLeaf(Tree tree, int id)
    {
        Assert.Equal(id, tree.Id);
        Assert.True(tree.IsLeaf);
    }
}
using System;
using System.Collections.Generic;
using System.Linq;

public class TreeBuildingRecord
{
    public int ParentId { get; set; }
    public int RecordId { get; set; }
}

public class Tree
{
    public int Id { get; set; }
    public int ParentId { get; set; }

    public List<Tree> Children { get; set; }

    public Tree(TreeBuildingRecord record)
    {
        Id = record.RecordId;
        ParentId = record.ParentId;
        Children = new List<Tree>();
    }

    public bool IsLeaf => Children.Count == 0;
}

public static class TreeBuilder
{
    public static Tree BuildTree(IEnumerable<TreeBuildingRecord> records)
    {
        if (records.Count() == 0
            || records.Any(record =>
                (record.RecordId == 0 && record.ParentId != 0)
                || (record.RecordId != 0 && record.ParentId >= record.RecordId)
                || (record.RecordId >= records.Count())))
        {
            throw new ArgumentException();
        }

        records = records.OrderBy(rec => rec.RecordId);

        var trees = new List<Tree>();
        foreach (var record in records)
        {
            var t = new Tree(record);
            trees.Add(t);
            if (t.Id > 0)
            {
                var parent = trees[t.ParentId];
                parent.Children.Add(t);
            }
        }

        return trees[0];
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?