binary-tree.coffee

class BinaryTree
  constructor: () ->

class BinaryTreeNode extends BinaryTree
  constructor: (@value, @left, @right) ->Object.freeze(@)
  isEmpty: () -> false
  depth: () -> 1 + Math.max(@left.depth(), @right.depth())
  count: () -> 1 + @left.count() + @right.count()

  inorder: (fn) -> @left.inorder(fn); fn(@value); @right.inorder(fn)
  preorder: (fn) -> fn(@value); @left.preorder(fn); @right.preorder(fn)
  postorder: (fn) -> @left.postorder(fn); @right.postorder(fn); fn(@value)

  contains: (x) ->
    return true if x == @value
    return @right.contains(x) if x > @value
    return @left.contains(x)

  insert: (x) ->
    if x > @value
      return new BinaryTreeNode(@value, @left, @right.insert(x))
    else
      return new BinaryTreeNode(@value, @left.insert(x), @right)

  remove: (x) ->
    if x < @value and @left.contains x
      return new BinaryTreeNode(@value, @left.remove(x), @right)

    if x > @value and @right.contains x
      return new BinaryTreeNode(@value, @left, @right.remove(x))

    return this unless x == @value
    return @left if @right.isEmpty()
    return @right if @left.isEmpty()

    left_values = []
    @left.postorder (v) -> left_values.push v
    left_values = left_values.sort (a, b) -> a - b
    max_left = left_values.pop()

    result = new BinaryTreeNode(max_left, new EmptyBinaryTree(), @right)

    for v in left_values
      result = result.insert v

    result

class EmptyBinaryTree extends BinaryTree
  constructor: () -> Object.freeze(@)
  isEmpty: () -> true
  depth: () -> 0
  count: () -> 0
  inorder: (fn) ->
  preorder: (fn) ->
  postorder: (fn) ->
  contains: (x) -> false
  insert: (x) -> new BinaryTreeNode(x, this, this)
  remove: (x) -> this