binary_tree.nim

discard """
Run as following.
  $ nim c -r binary_tree.nim
"""

type
  Node*[T] = ref NodeObj[T]
  NodeObj[T] = object
    left: Node[T]
    right: Node[T]
    value: T


proc new_node*[T](value: T): Node[T] =
  new(result)
  result.value = value


proc is_leaf_node*[T](node: Node[T]): bool =
  return node.left.isNil and node.right.isNil


proc insert_node*[T](node: Node[T], value: T): Node[T] =
  if node.isNil:
    return new_node(value)
  var n = node
  while not n.isNil:
    if n.value < value:
      if n.right.isNil:
        n.right = new_node(value)
        break
      else:
        n = n.right
    elif n.value > value:
      if n.left.isNil:
        n.left = new_node(value)
        break
      else:
        n = n.left
    else:
      raise newException(ValueError, "duplication value")
  return node


proc find_and_remove_min_node[T](node: Node[T]): Node[T] =
  var parent_node: Node[T] = nil
  var n = node
  while not n.left.isNil:
    parent_node = n
    n = n.left
  if not parent_node.isNil:
    parent_node.left = n.right
  return n


proc remove_node*[T](node: Node[T], parent: Node[T], value: T): Node[T] =
  if node.isNil:
    return node
  if node.value < value:
    return remove_node(node.right, node, value)
  elif node.value > value:
    return remove_node(node.left, node, value)
  else:
    var move_node: Node[T] = nil
    if not node.left.isNil and not node.right.isNil:
      move_node = find_and_remove_min_node(node.right)
      move_node.left = node.left
      if node.right != move_node:
        move_node.right = node.right
    elif not node.left.isNil:
      move_node = node.left
    elif not node.right.isNil:
      move_node = node.right
    if not parent.isNil:
      if parent.right == node:
        parent.right = move_node
      elif parent.left == node:
        parent.left = move_node
    return move_node


proc traverse_node*[T](node: Node[T], fn: proc(node: Node[T])) =
  if node.isNil:
    return
  traverse_node(node.left, fn)
  fn(node)
  traverse_node(node.right, fn)


type BinaryTree*[T] = ref object of RootObj
  root_node: Node[T]

method insert[T](this: BinaryTree[T], value: T) =
  if this.root_node.isNil:
    this.root_node = insert_node(this.root_node, value)
  else:
    discard insert_node(this.root_node, value)

method print[T](this: BinaryTree[T]) =
  traverse_node(this.root_node, proc (node: Node[T]) = echo(node.value))

method remove[T](this: BinaryTree[T], value: T) =
  if this.root_node.value == value:
    this.root_node = remove_node(this.root_node, nil, value)
  else:
    discard remove_node(this.root_node, nil, value)


echo("=============new=============")
let tree1: BinaryTree[int] = BinaryTree[int]()
tree1.insert(5)
tree1.insert(3)
tree1.insert(2)
tree1.insert(4)
tree1.insert(9)
tree1.insert(7)
tree1.insert(8)
tree1.insert(10)
echo("-----------------------------")
tree1.print()
echo("-----------------------------")
tree1.remove(5)
tree1.print()


echo("=============new=============")
let tree2: BinaryTree[int] = BinaryTree[int]()
tree2.insert(5)
tree2.insert(3)
tree2.insert(2)
tree2.insert(4)
tree2.insert(9)
echo("-----------------------------")
tree2.print()
echo("-----------------------------")
tree2.remove(5)
tree2.remove(3)
tree2.remove(4)
tree2.remove(9)
tree2.remove(2)
tree2.print()

Thanks