binarytree.rb

module BinaryTree
  class Node
    attr_reader :word, :count
    attr_accessor :left, :right

    include Enumerable

    def initialize(word)
      @word = word
      @count = 1
    end

    def insert(node)
      if node.word == word
        increment_count(1)
      elsif node.word < word
        insert_into(:left, node)
      else
        insert_into(:right, node)
      end
    end

    def words
      self.map { |node| node.word }
    end

    def size
      self.inject(0) { |sum, node| sum + 1 }
    end

    def count_all
      self.inject(0) { |sum, node| sum + node.count }
    end

    def each
      left.each {|node| yield node } unless left.nil?
      yield self
      right.each {|node| yield node } unless right.nil?
    end

  private
    def increment_count(amount)
      @count += amount
    end

    def insert_into(pos, node)
      child = self.send(pos)
      child ? child.insert(node) : self.send("#{pos}=", node)
    end
  end
end

binarytree_spec.rb

require 'rspec'
require './binarytree'

include BinaryTree

RSpec.describe Node do
  shared_examples 'Node with word "foo"' do
    it "should have word equal to 'foo'" do
      expect(subject.word).to eq('foo')
    end
  end

  shared_examples 'Node with no children' do
    it "should be nil on the left" do
      expect(subject.left).to be_nil
    end
    
    it "should be nil on the right" do
      expect(subject.right).to be_nil
    end
  end

  shared_examples 'Node with one child with no children' do
    it "should have a size of 2" do
      expect(subject.size).to eq(2)
    end
  end

  shared_examples 'Node with two children with no children' do
    it "should have a size of 3" do
      expect(subject.size).to eq(3)
    end
  end

  context 'with word "foo" and no children' do
    subject { Node.new('foo') }

    it_should_behave_like 'Node with word "foo"'
    it_should_behave_like 'Node with no children'

    it "should have a size of 1" do
      expect(subject.size).to eq(1)
    end

    it "should have a count of 1" do
      expect(subject.count).to eq(1)
    end

    it "should have have an array of words" do
      expect(subject.words).to eq(['foo'])
    end

    it "should have a total count of 1" do
      expect(subject.count_all).to eq(1)
    end
  end

  context 'with word "foo" and inserted a node with word "bar"' do
    before do
      @node = Node.new('foo')
      @node.insert(Node.new('bar'))
    end

    subject { @node }

    it_should_behave_like 'Node with word "foo"'
    it_should_behave_like 'Node with one child with no children'

    it 'should be nil on the right' do
      expect(subject.right).to be_nil
    end

    it 'should return an array of words' do
      expect(subject.words).to eq(['bar', 'foo'])
    end
    it "should have a total count of 2" do
      expect(subject.count_all).to eq(2)
    end

    describe 'its child on the left' do
      subject { @node.left }

      it_should_behave_like 'Node with no children'

      it 'should have a different word' do
        expect(subject.word).to eq('bar')
      end

      it 'should have a size of 1' do
        expect(subject.size).to eq(1)
      end

      it 'should have a count of 1' do
        expect(subject.count).to eq(1)
      end

      it 'should have a total count of 1' do
        expect(subject.count_all).to eq(1)
      end
    end
  end

  context 'with word "foo" and inserted a node with word "hoge"' do
    before do
      @node = Node.new('foo')
      @node.insert(Node.new('hoge'))
    end

    subject { @node }

    it_should_behave_like 'Node with word "foo"'
    it_should_behave_like 'Node with one child with no children'

    it 'should not have a left child' do
      expect(subject.left).to be_nil
    end

    it 'should return the correct words' do
      expect(subject.words).to eq(['foo', 'hoge'])
    end

    it 'should have a total count of 2' do
      expect(subject.count_all).to eq(2)
    end

    describe 'its child on the right' do
      subject { @node.right }

      it_should_behave_like 'Node with no children'

      it 'should have a different word' do
        expect(subject.word).to eq('hoge')
      end

      it 'should have a size of 1' do
        expect(subject.size).to eq(1)
      end

      it 'should have a count of 1' do
        expect(subject.count).to eq(1)
      end

      it 'should have a total count of 1' do
        expect(subject.count_all).to eq(1)
      end
    end
  end

  context 'with word "foo" and inserted a node with word "foo"' do
    subject do
      node = Node.new('foo')
      node.insert(Node.new('foo'))
      node
    end

    it_should_behave_like 'Node with word "foo"'
    it_should_behave_like 'Node with no children'

    it 'should have a count of 2' do
      expect(subject.count).to eq(2)
    end

    it 'should return a single word' do
      expect(subject.word).to eq('foo')
    end

    it 'should have a total count of 2' do
      expect(subject.count_all).to eq(2)
    end
  end

  context 'with word "foo" and inserted a node with word "bar" 3 times' do
    before do
      @node = Node.new('foo')
      3.times { @node.insert(Node.new('bar')) }
    end

    subject { @node }

    it_should_behave_like 'Node with word "foo"'

    it 'should not have a right child' do
      expect(subject.right).to be_nil
    end

    it 'should have a count of 1' do
      expect(subject.count).to eq(1)
    end

    it 'should have a size of 2' do
      expect(subject.size).to eq(2)
    end

    it 'should return the correct words' do
      expect(subject.words).to eq(['bar', 'foo'])
    end

    it 'should have a total count of 4' do
      expect(subject.count_all).to eq(4)
    end

    describe 'its child on the left' do
      subject { @node.left }

      it 'should have the correct word' do
        expect(subject.word).to eq('bar')
      end

      it 'should have a size of 1' do
        expect(subject.size).to eq(1)
      end

      it 'should have a count of 3' do
        expect(subject.count).to eq(3)
      end

      it 'should have a total count of 3' do
        expect(subject.count_all).to eq(3)
      end
    end
  end

  context 'with word "foo" and inserted a node with word "hoge" 3 times' do
    before do
      @node = Node.new('foo')
      3.times { @node.insert(Node.new('hoge')) }
    end

    subject { @node }

    it_should_behave_like 'Node with word "foo"'

    it 'should not have a left child' do
      expect(subject.left).to be_nil
    end

    it 'should have a count of 1' do
      expect(subject.count).to eq(1)
    end

    it 'should have a size of 2' do
      expect(subject.size).to eq(2)
    end

    it 'should return the correct words' do
      expect(subject.words).to eq(['foo', 'hoge'])
    end

    it 'should have a total count of 4' do
      expect(subject.count_all).to eq(4)
    end

    describe 'its child on the right' do
      subject { @node.right }

      it 'should have the correct word' do
        expect(subject.word).to eq('hoge')
      end

      it 'should have a size of 1' do
        expect(subject.size).to eq(1)
      end

      it 'should have a count of 3' do
        expect(subject.count).to eq(3)
      end

      it 'should have a total count of 3' do
        expect(subject.count_all).to eq(3)
      end
    end
  end

  context 'with word "a" and inserted nodes with word "b" ~ "j"' do
    before do
      @node = Node.new('a')
      %w{b c d e f g h i j}.each do |word|
        @node.insert(Node.new(word))
      end
    end

    subject { @node }

    it 'should have a size of 10' do
      expect(subject.size).to eq(10)
    end

    it 'should return all the correct words' do
      expect(subject.words).to eq(%W{a b c d e f g h i j})
    end
  end
end

example.rb

require './binarytree'

include BinaryTree

$root = nil
%w{to be or not to be}.each do |word|
  if $root.nil?
    $root = Node.new(word)
  else
    $root.insert(Node.new(word))
  end
end

$root.each do |node|
  puts "#{node.word} (#{node.count})"
end

puts
puts "#{$root.size} words."
puts "#{$root.count_all} nodes."