Tin

Examples · 7 of 339

07-tree

A recursive sum type: an immutable binary search tree.

examples/07-tree.tintin 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