Skip to content

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
end
  • Tree<T> is a generic enum, Leaf or a Node with named left, value and right fields, as binary-search-tree has it. The canonical data’s empty object {} is .Leaf.
  • tree_from_traversals is generic over any T: Hashable and Equatable and answers Result<Tree<T>, Error>. The three canonical errors are an Error enum, 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.
  • build takes the traversals apart with a list pattern: the head of the pre-order is the root, Iter.take_while reads the in-order up to it as the left subtree, and Iter.take and Iter.drop cut the rest of both lists at that size. The validation has already run, so build cannot meet a root missing from the in-order and has no error path.
  • The tests use String items, as the canonical data does. leaf keeps the expected trees short. The canonical cases are two subtests tables, the trees and the rejections, since they assert different shapes. The empty tree in the first row is written Tree.Leaf, which gives the table its type.