Simple binary search tree

binary_search_tree.rb

class BinarySearchTree

  Node = Struct.new(:key, :left, :right)
  attr_reader :root

  def initialize(root=nil, *keys)
    @root = Node.new(root)
    build_tree(*keys) unless keys.empty?
  end

  def ordered_keys
    @ordered_keys = []
    traverse
    @ordered_keys
  end

  def find(value)
    node = root
    until node.nil?
      if node.key > value
        node = node.left
      elsif node.key < value
        node = node.right
      elsif node.key == value
        return true
      end
    end
    false
  end

  private

    def build_tree(*key_values)
      key_values.each { |key| insert_node(key) }
    end

    def insert_node(value)
      node = root
      until node.nil?
        if node.key > value && node.left
          node = node.left
        elsif node.key < value && node.right
          node = node.right
        elsif node.key > value
          node.left = Node.new(value)
          return value
        elsif node.key < value
          node.right = Node.new(value)
          return value
        elsif node.key == value
          return value
        end
      end
    end

    def add_key(node_key)
      @ordered_keys << node_key
    end

    def traverse(node=@root)
      return if node.nil?
      traverse(node.left)
      add_key(node.key)
      traverse(node.right)
    end
end

Code kata to create and search a binary tree of integers.

Example usage

$ unordered_keys = [ 12, 85, 3, 90, 4, 17, 276, 11 ]
# => [ 12, 85, 3, 90, 4, 17, 276, 11 ]

$ tree = BinarySearchTree.new(*unordered_keys)
# => #<BinarySearchTree:0x00000000fa29b8 @root=#<struct BinarySearchTree::Node ...

$ tree.ordered_keys
# => [3, 4, 11, 12, 17, 85, 90, 276]

$ tree.find(10)
# => false

$ tree.find(11)
# => true