gistfile1.rb

class Mytree
  attr_accessor :left, :right
  attr_accessor :value
  
  def initialize(v)
    self.value = v
  end
  
  def print_preorder
    print
    left.print_preorder if left
    right.print_preorder if right
  end
  
  def print_inorder
    left.print_inorder if left
    print
    right.print_inorder if right
  end
  
  def print_postorder
    left.print_postorder if left
    right.print_postorder if right
    print
  end
  
  private
  def print
    STDOUT.write "#{value} " if value
  end
end


def tree_from_inorder_and_preorder(inorder, preorder)
  return nil if inorder.count == 0
  root = Mytree.new(preorder.first)
  left_inorder = []
  left_preorder = []
  right_inorder = []
  right_preorder = []
  found_root = false

  
  Array(0..inorder.count).each do |i|
    if inorder.at(i) == root.value
      found_root = true
    else
      unless found_root
        left_inorder << inorder.at(i)
        left_preorder << preorder.at(i+1) if preorder.at(i+1)
      else
        right_inorder << inorder.at(i)
        right_preorder << preorder.at(i) if preorder.at(i)
      end
    end
  end
  root.left = tree_from_inorder_and_preorder(left_inorder, left_preorder)
  root.right = tree_from_inorder_and_preorder(right_inorder, right_preorder)
  root
end


inorder   = ["a", "d", "c", "g", "b", "h", "e", "f", "i" ]
preorder  = ["c", "d", "a", "f", "g", "h", "b", "e", "i" ]

tree = tree_from_inorder_and_preorder(inorder, preorder)

tree.print_inorder
puts
tree.print_preorder
puts
tree.print_postorder