Binary Tree implemented in Ruby.

binarytree.rb

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

    include Enumerable

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

    def size
      size = 1
      size += @left.size  unless left.nil?
      size += @right.size unless right.nil?
      size
    end

    def insert(another_one)
      case @word <=> another_one.word
        when 1
          insert_into(:left, another_one)
        when 0
          @count += 1
        when -1
          insert_into(:right, another_one)
      end
    end

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

    def words
      entries.map {|e| e.word }
    end

    def count_all
      self.map { |node| node.count }.reduce(:+)
    end

    def insert_into(destination, another_one)
      var = destination.to_s
      eval(%Q{
        if @#{var}.nil?
          @#{var} = another_one
        else
          @#{var}.insert(another_one)
        end
      })
    end

    protected :insert_into
  end
end

binarytree_spec.rb

require 'rspec'
require './binarytree'

include BinaryTree

describe Node do
  share_examples_for 'Node with word "foo"' do
    its(:word)  { should == 'foo' }
  end

  share_examples_for 'Node with one child with no children' do
    its(:size) { should == 2 }
  end

  share_examples_for 'Node with two children with no children' do
    its(:size) { should == 3 }
  end

  share_examples_for 'Node with no children' do
    its(:left)  { should be_nil }
    its(:right) { should be_nil }
  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'

    its(:size)  { should == 1 }
    its(:count) { should == 1 }
    its(:words) { should == ['foo'] }
    its(:count_all) { should == 1 }
  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'

    its(:right) { should be_nil }
    its(:words) { should == ['bar', 'foo'] }
    its(:count_all) { should == 2 }

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

      it_should_behave_like 'Node with no children'

      its(:word)  { should == 'bar' }
      its(:size)  { should == 1 }
      its(:count) { should == 1 }
      its(:count_all) { should == 1 }
    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'

    its(:left)  { should be_nil }
    its(:words) { should == ['foo', 'hoge'] }
    its(:count_all) { should == 2 }

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

      it_should_behave_like 'Node with no children'

      its(:word)  { should == 'hoge' }
      its(:size)  { should == 1 }
      its(:count) { should == 1 }
      its(:count_all) { should == 1 }
    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'

    its(:count) { should == 2 }
    its(:words) { should == ['foo'] }
    its(:count_all) { should == 2 }
  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"'

    its(:right) { should be_nil }
    its(:count) { should == 1 }
    its(:size)  { should == 2 }
    its(:words) { should == ['bar', 'foo'] }
    its(:count_all) { should == 4 }

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

      its(:word)  { should == 'bar' }
      its(:size)  { should == 1 }
      its(:count) { should == 3 }
      its(:count_all) { should == 3 }
    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"'

    its(:left)  { should be_nil }
    its(:count) { should == 1 }
    its(:size)  { should == 2 }
    its(:words) { should == ['foo', 'hoge'] }
    its(:count_all) { should == 4 }

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

      its(:word)  { should == 'hoge' }
      its(:size)  { should == 1 }
      its(:count) { should == 3 }
      its(:count_all) { should == 3 }
    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 }

    its(:size)  { should == 10 }
    its(:words) { should == %w{a b c d e f g h i j} }
  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."

served as good source for understanding rspec syntax.. Thanks

You're welcome :)

I was searching for ruby tree implementations in web and this is the most easily understand implementation I found, thanks a lot. and RSpec tests are very valuable, learnt lots of new usages

thanks again

I feel like the initialize of the BinaryTree::Node is a bit confusing. In such a small case, it really doesn't make sense to me to use ruby's parallel assignment. In the interest of readable code, I think it would make more sense to do

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

over

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

Just my two cents. Regardless, this was extraordinarily helpful. Thanks!

Nice One..thanks :)

@yuya-takeyama thanks for posting this. I enjoyed using your specs to drive my own implementation while working on Ruby Kata 11: Sorting It Out.

Thanks for sharing.
Btw, it's not just a binary tree: it's a binary search tree.

Nice

How to find depth of the binary tree?

Hi @yuya-takeyama,

is it recursion function?

    def size
      size = 1
      size += @left.size  unless left.nil?
      size += @right.size unless right.nil?
      size
    end

@Aravin, yes it is. When you call size on the node, it calls size on each subsequent node. So when you reach the bottom of the tree, meaning node that doesn't have any children, it returns sum, which is 1 and then travels up.