Examples · 7 of 339
07-tree
A recursive sum type: an immutable binary search tree.
tin run examples/07-tree.tin// A recursive sum type: an immutable binary search tree.
type Tree =
| Leaf
| Node { left: Tree, value: int, right: Tree }
fn insert(t: Tree, v: int): Tree => match t {
Leaf => Node { left: Leaf, value: v, right: Leaf }
Node { left, value, right } =>
if v < value { Node { left: insert(left, v), value, right } }
else if v > value { Node { left, value, right: insert(right, v) } }
else { t }
}
fn contains(t: Tree, v: int): bool => match t {
Leaf => false
Node { left, value, right } =>
if v == value { true } else if v < value { contains(left, v) } else { contains(right, v) }
}
fn depth(t: Tree): int => match t {
Leaf => 0
Node { left, right } => 1 + max(depth(left), depth(right))
}
fn inOrder(t: Tree, out: inout int[]) {
match t {
Leaf => {}
Node { left, value, right } => {
inOrder(left, &out)
out.push(value)
inOrder(right, &out)
}
}
}
fn main() {
var tree: Tree = Leaf
for v in [50, 30, 70, 20, 40, 60, 80, 30] {
tree = insert(tree, v)
}
var sorted: int[] = []
inOrder(tree, &sorted)
print(sorted)
print("depth: {depth(tree)}")
print("contains 60? {contains(tree, 60)}")
print("contains 65? {contains(tree, 65)}")
} [20, 30, 40, 50, 60, 70, 80]
depth: 3
contains 60? true
contains 65? false