Skip to content

Tree Building

Rebuild a forum’s tree of posts from unordered records of an id and a parent id, rejecting records that do not form a tree.

Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.

// FILE: tree_building.nomi
//# Builds a tree of posts from records of ids and parent ids.

/// One post as it is stored: its id and its parent's id. The root's parent
/// is itself.
pub struct Record
    id:     Int
    parent: Int
end

/// A post and its replies, ordered by id.
pub struct Node
    id:       Int
    children: List<Node> = []
end

/// Why the records do not make a tree.
pub enum Error
    RootHasParent
    InvalidRecord
end

impl Display for Error
    fn to_string(error: Error) -> String
        case error
            .RootHasParent -> "node parent_id should be smaller than its record_id"
            .InvalidRecord -> "record id is invalid or out of order"
        end
    end
end

/// The tree of `records`, in any order, or `None` for no records. The ids
/// must be 0 to one less than the number of records, each once; the root,
/// 0, is its own parent, and every other record's parent has a lower id.
pub fn build_tree(records: List<Record>) -> Result<Maybe<Node>, Error>
    sorted = Iter.sort_by(records, .id)

    ids_in_order =
        sorted
        |> Iter.with_index()
        |> Iter.all_match(fn (index, record) -> record.id == index)

    if not ids_in_order then return Err(.InvalidRecord)

    case sorted
        [] ->
            Ok(None)

        [root, ..] when root.parent != 0 ->
            Err(.RootHasParent)

        [_root, ..rest] when Iter.any_match(rest, fn record -> record.parent >= record.id) ->
            Err(.InvalidRecord)

        [_root, ..rest] ->
            Ok(Some(node(0, Iter.group_by(rest, .parent))))
    end
end

/// The node `id` with its replies, from each parent's child records in id
/// order.
fn node(id: Int, children: Map<Int, List<Record>>) -> Node
    replies = Map.get(children, id) |> Maybe.with_default([])

    {id:, children: replies |> Iter.map(&node(&1.id, children)) |> Iter.to_list()}
end

// FILE: tree_building_test.nomi
import tree_building.{self, Node, Record}

/// A node with no replies.
fn leaf(id: Int) -> Node
    {id:}
end

test "build tree"
    cases: List<(String, List<Record>, Maybe<Node>)> = [
        ("empty list",    [],                   None),
        ("single record", [{id: 0, parent: 0}], Some(leaf(0))),
        (
            "three records in order",
            [{id: 0, parent: 0}, {id: 1, parent: 0}, {id: 2, parent: 0}],
            Some({id: 0, children: [leaf(1), leaf(2)]}),
        ),
        (
            "three records in reverse order",
            [{id: 2, parent: 0}, {id: 1, parent: 0}, {id: 0, parent: 0}],
            Some({id: 0, children: [leaf(1), leaf(2)]}),
        ),
        (
            "more than two children",
            [{id: 0, parent: 0}, {id: 1, parent: 0}, {id: 2, parent: 0}, {id: 3, parent: 0}],
            Some({id: 0, children: [leaf(1), leaf(2), leaf(3)]}),
        ),
        (
            "binary tree",
            [
                {id: 5, parent: 1},
                {id: 3, parent: 2},
                {id: 2, parent: 0},
                {id: 4, parent: 1},
                {id: 1, parent: 0},
                {id: 0, parent: 0},
                {id: 6, parent: 2},
            ],
            Some({
                id: 0,
                children: [
                    {id: 1, children: [leaf(4), leaf(5)]},
                    {id: 2, children: [leaf(3), leaf(6)]},
                ],
            }),
        ),
        (
            "unbalanced tree",
            [
                {id: 5, parent: 2},
                {id: 3, parent: 2},
                {id: 2, parent: 0},
                {id: 4, parent: 1},
                {id: 1, parent: 0},
                {id: 0, parent: 0},
                {id: 6, parent: 2},
            ],
            Some({
                id: 0,
                children: [
                    {id: 1, children: [leaf(4)]},
                    {id: 2, children: [leaf(3), leaf(5), leaf(6)]},
                ],
            }),
        ),
    ]

    subtests cases, (description, records, expected), description
        assert tree_building.build_tree(records) == Ok(expected)
    end
end

test "invalid records"
    cases: List<(String, List<Record>, String)> = [
        (
            "one root node and has parent",
            [{id: 0, parent: 1}],
            "node parent_id should be smaller than its record_id",
        ),
        (
            "root node has parent",
            [{id: 0, parent: 1}, {id: 1, parent: 0}],
            "node parent_id should be smaller than its record_id",
        ),
        (
            "no root node",
            [{id: 1, parent: 0}, {id: 2, parent: 0}],
            "record id is invalid or out of order",
        ),
        (
            "duplicate node",
            [{id: 0, parent: 0}, {id: 1, parent: 0}, {id: 1, parent: 0}],
            "record id is invalid or out of order",
        ),
        (
            "duplicate root",
            [{id: 0, parent: 0}, {id: 0, parent: 0}],
            "record id is invalid or out of order",
        ),
        (
            "non-continuous",
            [{id: 2, parent: 0}, {id: 4, parent: 2}, {id: 1, parent: 0}, {id: 0, parent: 0}],
            "record id is invalid or out of order",
        ),
        (
            "cycle directly",
            [
                {id: 5, parent: 2},
                {id: 3, parent: 2},
                {id: 2, parent: 2},
                {id: 4, parent: 1},
                {id: 1, parent: 0},
                {id: 0, parent: 0},
                {id: 6, parent: 3},
            ],
            "record id is invalid or out of order",
        ),
        (
            "cycle indirectly",
            [
                {id: 5, parent: 2},
                {id: 3, parent: 2},
                {id: 2, parent: 6},
                {id: 4, parent: 1},
                {id: 1, parent: 0},
                {id: 0, parent: 0},
                {id: 6, parent: 3},
            ],
            "record id is invalid or out of order",
        ),
        (
            "higher id parent of lower id",
            [{id: 0, parent: 0}, {id: 2, parent: 0}, {id: 1, parent: 2}],
            "record id is invalid or out of order",
        ),
    ]

    subtests cases, (description, records, message), description
        assert Err(error) = tree_building.build_tree(records)
        assert "${error}" == message
    end
end
  • The exercise is a refactoring of slow code that each track supplies; there is no slow version here, only the tree built directly.
  • Record and Node are structs. Node’s children defaults to [], so a leaf is {id:}, and the tests compare whole trees with ==, which compares a struct field by field with no derive Equatable.
  • build_tree returns Result<Maybe<Node>, Error>: no records is Ok(None), the canonical empty answer, not an error. Error has two variants for the canonical two messages, given by its Display.
  • The records are sorted by id once. They are valid ids exactly when the sorted record at each index has that index as its id, which Iter.with_index and Iter.all_match check in one pass; that catches a missing root, a duplicate and a gap alike.
  • The canonical data splits the remaining rules oddly, and the solution follows it: a root whose parent is not 0 is the “parent_id should be smaller” error, but any other record whose parent is not lower than its id, a cycle included, is “record id is invalid or out of order”. These are three arms of one case on the sorted list, two with when guards.
  • Once every parent is lower than its child, the records cannot form a cycle, so the tree is built by Iter.group_by on the parent, which keeps each parent’s children in id order, and a recursive node from the root.
  • The valid and invalid cases are two subtests tables. The invalid table asserts each error’s message, which is what the canonical data gives. leaf keeps the expected trees short.