Binary tree value equality.

binary_tree_equality.rb

require 'tree'
require 'rspec'

#       2
#   /      \
# 1        4
#         /
#       3
# 
# 
#      2
#   /      \
# 1        3
#             \
#               4


class BinaryTreeEquality
  def self.bt_equal_lazy?(left_tree, right_tree)
    left_tree.map(&:content).sort == right_tree.map(&:content).sort
  end

  def initialize(left_tree, right_tree)
    @left_tree = left_tree
    @right_tree = right_tree
  end

  def equal?
    return AsArray.new(@left_tree).values.sort == AsArray.new(@right_tree).values.sort
  end

  class AsArray
    def initialize(node)
      @node = node
      @list = []

      traverse(@node)
    end

    def values
      @list.map(&:content)
    end

    def traverse(root)
      @list.push(root)
      if root.children
        root.children.each do |n|
          traverse(n)
        end
      end  
    end
  end
end

describe "BinaryTreeEquality" do
  def left_tree
    root = Tree::TreeNode.new("2", 2)
    root << Tree::TreeNode.new("1", 1)

    child = Tree::TreeNode.new("4", 4)
    root << child
    child << Tree::TreeNode.new("3", 3) 

    root
  end
  def right_tree
    root = Tree::TreeNode.new("2", 2)
    root << Tree::TreeNode.new("1", 1)

    child = Tree::TreeNode.new("3", 3)
    root << child
    child << Tree::TreeNode.new("4", 4) 

    root
  end
  def wrong_tree
    root = Tree::TreeNode.new("2", 2)
    root << Tree::TreeNode.new("1", 1)

    child = Tree::TreeNode.new("3", 3)
    root << child
    child << Tree::TreeNode.new("3child", 3) 

    root
  end

  describe ".bt_equal_lazy?" do
    it "returns true if two binary trees contain the same numbers" do
      BinaryTreeEquality.bt_equal_lazy?(left_tree, right_tree).should be_true
    end

    it "returns false if two binary trees do not contain the same numbers" do
      BinaryTreeEquality.bt_equal_lazy?(left_tree, wrong_tree).should be_false
      BinaryTreeEquality.bt_equal_lazy?(right_tree, wrong_tree).should be_false
    end
  end

  describe "#equal?" do
    it "returns true if two binary trees contain the same numbers" do
      BinaryTreeEquality.new(left_tree, right_tree).equal?.should be_true
    end

    it "returns false if two binary trees do not contain the same numbers" do
      BinaryTreeEquality.new(left_tree, wrong_tree).equal?.should be_false
      BinaryTreeEquality.new(right_tree, wrong_tree).equal?.should be_false
    end
  end
end

gistfile1.sh

Expected output:

10:48punk fib-ruby> rspec binary_trees.rb 

BinaryTreeEquality
  .bt_equal_lazy?
    returns true if two binary trees contain the same numbers
    returns false if two binary trees do not contain the same numbers
  #equal?
    returns true if two binary trees contain the same numbers
    returns false if two binary trees do not contain the same numbers

Finished in 0.003 seconds
4 examples, 0 failures