btree.swift

import UIKit

indirect enum Tree<Element : Comparable> {
  case Empty
  case Node(Element, Tree<Element>, Tree<Element>)

  init() {
    self = .Empty
  }

  init(value: Element, left: Tree<Element> = .Empty, right: Tree<Element> = .Empty) {
    self = .Node(value, left, right)
  }

}

func insertElement<T>(root: Tree<T>, _ x: T) -> Tree<T> {

  guard case let .Node(y, left, right) = root else {
    return Tree(value: x)
  }

  if x < y { return Tree(value: y, left: insertElement(left, x), right: right) }
  if x > y { return Tree(value: y, left: left, right: insertElement(right, x)) }
  
  return root
}

extension Tree {

  func insert(element: Element) -> Tree {
    guard case let .Node(y, left, right) = insertElement(self, element) else {
      fatalError("Empty!")
    }

    return .Node(y, left, right)
  }

  func contains(element: Element) -> Bool {
    guard case let .Node(value, left, right) = self else {
      return false
    }
    if element < value { return left.contains(element) }
    if element > value { return right.contains(element) }
    return true
  }

}


var t: Tree<String> = .Empty
t = t.insert("hello")
t = t.insert("hello 2")

t.contains("hello")
t.contains("hello 3")