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
endok data is inserted (5 cases)
ok can sort data (5 cases)
test result: ok. 10 passed, 0 failed
How it’s written
Section titled “How it’s written”- The tree is a generic enum,
Tree<T>: aLeaf, or aNodewith namedleft,valueandrightfields. It is a value, soinsertreturns a new tree that shares the subtrees it did not change. insertis acasewith 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.frombuilds a tree byIter.reduceover the values from an empty tree, andsortedreads 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 useInts, 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 noderive Equatable. - The functions are in
impl Tree<T>, calledTree.from(values)andTree.sorted(tree)afterimport binary_search_tree.Tree. Each names the block’sT, so a call takes it from its tree or its values, andwhere T: Comparablenarrows the two that compare. - An empty tree is
.Leafwherever aTree<T>is expected: ininsert’s new node and in every expected tree of the tests.fromstarts itsIter.reducefromTree.Leaf, qualified, since nothing there says what type the starting value has. - The two canonical properties are two
subteststables. The shape table names the enum once, in its first row’sTree.Node{...}; the bare.Node{...}and.Leafin the later rows and inside each node takeTree<Int>from it.