Satellite
Rebuild a binary tree from its pre-order and in-order traversals, rejecting traversals that describe no tree.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: satellite.nomi
//# Rebuilds a binary tree from its preorder and inorder traversals.
/// A binary tree with a value at each node.
pub enum Tree<T>
Leaf
Node {left: Tree<T>, value: T, right: Tree<T>}
end
/// Why two traversals describe no tree.
pub enum Error
DifferentLengths
DifferentElements
RepeatedItems
end
/// The tree whose pre-order traversal is `preorder` and whose in-order
/// traversal is `inorder`. The two must hold the same items, each once.
pub fn tree_from_traversals<T>(
preorder: List<T>,
inorder: List<T>,
) -> Result<Tree<T>, Error> where T: Hashable and Equatable
items = Iter.to_set(preorder)
case
Iter.count(preorder) != Iter.count(inorder) -> Err(.DifferentLengths)
items != Iter.to_set(inorder) -> Err(.DifferentElements)
Set.size(items) != Iter.count(preorder) -> Err(.RepeatedItems)
_ -> Ok(build(preorder, inorder))
end
end
/// The tree of two traversals of the same unique items. The first item in
/// pre-order is the root; the items before it in in-order are its left
/// subtree, and as many items after it in pre-order are that subtree's
/// pre-order.
fn build<T>(preorder: List<T>, inorder: List<T>) -> Tree<T> where T: Equatable
case preorder
[] ->
.Leaf
[root, ..rest] ->
left_inorder =
inorder
|> Iter.take_while(&(&1 != root))
|> Iter.to_list()
size = Iter.count(left_inorder)
left_preorder = Iter.take(rest, size) |> Iter.to_list()
right_preorder = Iter.drop(rest, size) |> Iter.to_list()
right_inorder = Iter.drop(inorder, size + 1) |> Iter.to_list()
.Node{
left: build(left_preorder, left_inorder),
value: root,
right: build(right_preorder, right_inorder),
}
end
end
// FILE: satellite_test.nomi
import satellite.{self, Error, Tree}
/// A node with no subtrees.
fn leaf(value: String) -> Tree<String>
.Node{left: .Leaf, value:, right: .Leaf}
end
test "rebuilds the tree"
[
("Empty tree", [], [], Tree.Leaf),
("Tree with one item", ["a"], ["a"], leaf("a")),
(
"Tree with many items",
["a", "i", "x", "f", "r"],
["i", "a", "f", "x", "r"],
.Node{
left: leaf("i"),
value: "a",
right: .Node{left: leaf("f"), value: "x", right: leaf("r")},
},
),
(
"A degenerate binary tree",
["a", "b", "c", "d"],
["d", "c", "b", "a"],
.Node{
left: .Node{
left: .Node{left: leaf("d"), value: "c", right: .Leaf},
value: "b",
right: .Leaf,
},
value: "a",
right: .Leaf,
},
),
(
"Another degenerate binary tree",
["a", "b", "c", "d"],
["a", "b", "c", "d"],
.Node{
left: .Leaf,
value: "a",
right: .Node{
left: .Leaf,
value: "b",
right: .Node{left: .Leaf, value: "c", right: leaf("d")},
},
},
),
(
"Tree with many more items",
["a", "b", "d", "g", "h", "c", "e", "f", "i"],
["g", "d", "h", "b", "a", "e", "c", "i", "f"],
.Node{
left: .Node{
left: .Node{left: leaf("g"), value: "d", right: leaf("h")},
value: "b",
right: .Leaf,
},
value: "a",
right: .Node{
left: leaf("e"),
value: "c",
right: .Node{left: leaf("i"), value: "f", right: .Leaf},
},
},
),
]
|> subtests (description, preorder, inorder, expected), description
assert satellite.tree_from_traversals(preorder, inorder) == Ok(expected)
end
end
test "rejects traversals of no tree"
[
(
"Reject traversals of different length",
["a", "b"],
["b", "a", "r"],
Error.DifferentLengths,
),
(
"Reject inconsistent traversals of same length",
["x", "y", "z"],
["a", "b", "c"],
.DifferentElements,
),
(
"Reject traversals with repeated items",
["a", "b", "a"],
["b", "a", "a"],
.RepeatedItems,
),
]
|> subtests (description, preorder, inorder, expected), description
assert satellite.tree_from_traversals(preorder, inorder) == Err(expected)
end
endok rebuilds the tree (6 cases)
ok rejects traversals of no tree (3 cases)
test result: ok. 9 passed, 0 failed
How it’s written
Section titled “How it’s written”Tree<T>is a generic enum,Leafor aNodewith namedleft,valueandrightfields, as binary-search-tree has it. The canonical data’s empty object{}is.Leaf.tree_from_traversalsis generic over anyT: Hashable and Equatableand answersResult<Tree<T>, Error>. The three canonical errors are anErrorenum, checked in the canonical data’s order: the lengths, then the two sets of items, then whether the set is as large as the list, which finds a repeated item.buildtakes the traversals apart with a list pattern: the head of the pre-order is the root,Iter.take_whilereads the in-order up to it as the left subtree, andIter.takeandIter.dropcut the rest of both lists at that size. The validation has already run, sobuildcannot meet a root missing from the in-order and has no error path.- The tests use
Stringitems, as the canonical data does.leafkeeps the expected trees short. The canonical cases are twosubteststables, the trees and the rejections, since they assert different shapes. The empty tree in the first row is writtenTree.Leaf, which gives the table its type.