tree.rb

class Tree
  attr_accessor :name, :left, :right

  def initialize(name)
    @name = name
    @left = nil
    @right = nil
  end

  def leaf?
    @left.nil? && @right.nil?
  end

  def in_order
    order = []
    if @left
      order += @left.in_order
    end
    order << @name
    if @right
      order += @right.in_order
    end
    order
  end

  def post_order
    order = []
    if @left
      order += @left.post_order
    end

    if @right
      order += @right.post_order
    end
    order << @name

    order
  end
end

def make_tree(in_order, post_order)
  if in_order.empty? && post_order.empty?
    nil
  elsif in_order.size == 1 && post_order.size == 1
    Tree.new(in_order.first)
  else
    root = post_order.last
    i = in_order.index(root)

    left_in_order = in_order.take(i)
    left_post_order = post_order.take(i)

    right_in_order = in_order.drop(i + 1)
    right_post_order = post_order[i..-2] || []

    r = Tree.new(root)
    r.left = make_tree(left_in_order, left_post_order)
    r.right = make_tree(right_in_order, right_post_order)
    r
  end
end

$paths = []

def deep(tree, path)
  if tree.nil?

  elsif tree.leaf?
    full_path = path + [tree.name]
    $paths << full_path
    #puts full_path.join(' ')
  else
    deep(tree.left, path + [tree.name])
    deep(tree.right, path + [tree.name])
  end
end