Binary Search Tree

binary_tree.rb

class Node
  attr_accessor :value, :left, :right

  def initialize(value, left = nil, right = nil)
    @value, @left, @right = value, left, right
  end

  def delete(node)
    if @left.value == node.value
      @left = nil
    elsif @right.value == node.value
      @right = nil
    else
      nil
    end
  end

  def replace(node)
    if @left.value == node.value
      @left = node.left || node.right
    elsif @right.value == node.value
      @right = node.left || node.right
    else
      nil
    end
  end
end

class BinarySearchTree
  attr_accessor :root
  attr_reader :nodes

  def initialize(root = nil)
    @root = root
  end

  def insert(value, node = @root)
    new_node = Node.new(value)
    if node.nil?
      @root = new_node
    elsif value < node.value
      node.left.nil? ? node.left = new_node : insert(value, node.left)
    else
      node.right.nil? ? node.right = new_node : insert(value, node.right)
    end
  end

  def find(value, node = @root)
    if root.nil?
      -1
    elsif node.value == value
      node
    else
      value < node.value ? find(value, node.left) : find(value, node.right)
    end
  end

  def find_parent(value, node = @root)
    if value < node.value
      if node.left.value == value
        node
      else
        find_parent(value, node.left)
      end
    else
      if node.right.value == value
        node
      else
        find_parent(value, node.right)
      end
    end
  end

  def get_smallest_in_right_branch(node)
    if node.left
      get_smallest_in_right_branch(node.left)
    else
      node
    end
  end

  def delete(value)
    node = find(value)
    parent = find_parent(value)
    if node.left.nil? && node.right.nil?
      parent.delete(node)
    elsif node.left.nil? || node.right.nil?
      parent.replace(node)
    else
      smallest_to_the_right = get_smallest_in_right_branch(node.right)
      delete(smallest_to_the_right.value)
      node.value = smallest_to_the_right.value
    end
  end

  def get_tree_values(node = @root)
    values = []
    unless node.left.nil?
      values << node.left.value
      values += get_tree_values(node.left)
    end
    unless node.right.nil?
      values << node.right.value
      values += get_tree_values(node.right)
    end
    values
  end
end

tree = BinarySearchTree.new
[8, 3, 10, 14, 13, 1, 6, 4, 7].each { |x| tree.insert(x) }
p tree.find(14)
p tree.get_tree_values
tree.delete(3)
p tree.get_tree_values
tree.delete(10)
p tree.get_tree_values
tree.insert(10)
p tree.get_tree_values
p tree.find(10)