treecompare.rb

# U Suck At Coding Exercise: Tree Comparison
# Feb 28 2012
# @loganlinn

class TreeNode
  attr_accessor :value, :left, :right

  def initialize v
    @value = v
  end

  def left?
    !left.nil?
  end

  def right?
    !right.nil?
  end

  def == other
    self.class.trees_equal?(self, other)
  end

  def self.trees_equal?(tree1, tree2)
    # not equal if children don't match
    return false if (tree1.left? ^ tree2.left?) or
                    (tree1.right? ^ tree2.right?)
    (!tree1.left?  || trees_equal?(tree1.left,  tree2.left)) and
    (!tree1.right? || trees_equal?(tree1.right, tree2.right))
  end
end


tree1 = TreeNode.new :A
tree1.left  = TreeNode.new :D
tree1.right = TreeNode.new :C
tree1.left.left = TreeNode.new :B

tree2 = TreeNode.new :D
tree2.left  = TreeNode.new :A
tree2.right = TreeNode.new :C
tree2.left.left = TreeNode.new :B

tree3 = TreeNode.new :D
tree3.right = TreeNode.new :A
tree3.right.left  = TreeNode.new :C
tree3.right.right = TreeNode.new :B

puts tree1 == tree2 # => true
puts tree1 == tree3 # => false