Skip to content

Binary Search Tree

Insert values into a binary search tree, check the shape it builds, and read its values back in sorted order.

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

// FILE: binary_search_tree.nomi
//# A binary search tree, built by inserting values one at a time.

/// A binary search tree: every value in a node's left subtree is at most
/// its value, and every value in its right subtree is greater.
pub enum Tree<T>
    Leaf
    Node {left: Tree<T>, value: T, right: Tree<T>}
end

impl Tree<T>
    /// The tree that inserting `values` one after another into an empty
    /// tree builds.
    pub fn from(values: List<T>) -> Tree<T> where T: Comparable
        Iter.reduce(values, Tree.Leaf, Tree.insert)
    end

    /// `tree` with `value` added: to the left of a node at least as large,
    /// to the right of a smaller one.
    pub fn insert(tree: Tree<T>, value: T) -> Tree<T> where T: Comparable
        case tree
            .Leaf ->
                .Node{left: .Leaf, value:, right: .Leaf}

            .Node{left:, value: here, right:} when value <= here ->
                .Node{left: Tree.insert(left, value), value: here, right:}

            .Node{left:, value: here, right:} ->
                .Node{left:, value: here, right: Tree.insert(right, value)}
        end
    end

    /// Every value in `tree`, smallest first.
    pub fn sorted(tree: Tree<T>) -> List<T>
        case tree
            .Leaf                        -> []
            .Node{left:, value:, right:} -> [..Tree.sorted(left), value, ..Tree.sorted(right)]
        end
    end
end

// FILE: binary_search_tree_test.nomi
import binary_search_tree.Tree

test "data is inserted"
    [
        ("data is retained", [4], Tree.Node{left: .Leaf, value: 4, right: .Leaf}),
        (
            "smaller number at left node",
            [4, 2],
            .Node{
                left:  .Node{left: .Leaf, value: 2, right: .Leaf},
                value: 4,
                right: .Leaf,
            },
        ),
        (
            "same number at left node",
            [4, 4],
            .Node{
                left:  .Node{left: .Leaf, value: 4, right: .Leaf},
                value: 4,
                right: .Leaf,
            },
        ),
        (
            "greater number at right node",
            [4, 5],
            .Node{
                left:  .Leaf,
                value: 4,
                right: .Node{left: .Leaf, value: 5, right: .Leaf},
            },
        ),
        ("can create complex tree", [4, 2, 6, 1, 3, 5, 7], .Node{
            left: .Node{
                left:  .Node{left: .Leaf, value: 1, right: .Leaf},
                value: 2,
                right: .Node{left: .Leaf, value: 3, right: .Leaf},
            },
            value: 4,
            right: .Node{
                left:  .Node{left: .Leaf, value: 5, right: .Leaf},
                value: 6,
                right: .Node{left: .Leaf, value: 7, right: .Leaf},
            },
        }),
    ]
    |> subtests (description, values, expected), description
        assert Tree.from(values) == expected
    end
end

test "can sort data"
    [
        ("can sort single number",                          [2],                [2]),
        ("can sort if second number is smaller than first", [2, 1],             [1, 2]),
        ("can sort if second number is same as first",      [2, 2],             [2, 2]),
        ("can sort if second number is greater than first", [2, 3],             [2, 3]),
        ("can sort complex tree",                           [2, 1, 3, 6, 7, 5], [1, 2, 3, 5, 6, 7]),
    ]
    |> subtests (description, values, expected), description
        assert Tree.from(values) |> Tree.sorted() == expected
    end
end
  • The tree is a generic enum, Tree<T>: a Leaf, or a Node with named left, value and right fields. It is a value, so insert returns a new tree that shares the subtrees it did not change.
  • insert is a case with a guard: an empty tree becomes a node, a value at most the node’s goes left (when value <= here), and anything else goes right. That puts an equal value on the left, as the canonical “same number at left node” case asks.
  • from builds a tree by Iter.reduce over the values from an empty tree, and sorted reads it in order, left subtree, value, right subtree.
  • The functions are generic over any T: Comparable. The canonical data writes the values as strings ("4"), to stay out of each language’s number types; the tests use Ints, which is what the strings stand for.
  • The shape cases compare the built tree with the expected one, written as nested .Node{...} literals, with ==, which compares enums structurally and needs no derive Equatable.
  • The functions are in impl Tree<T>, called Tree.from(values) and Tree.sorted(tree) after import binary_search_tree.Tree. Each names the block’s T, so a call takes it from its tree or its values, and where T: Comparable narrows the two that compare.
  • An empty tree is .Leaf wherever a Tree<T> is expected: in insert’s new node and in every expected tree of the tests. from starts its Iter.reduce from Tree.Leaf, qualified, since nothing there says what type the starting value has.
  • The two canonical properties are two subtests tables. The shape table names the enum once, in its first row’s Tree.Node{...}; the bare .Node{...} and .Leaf in the later rows and inside each node take Tree<Int> from it.