Trie tree implementation in Ruby.

trie.rb

class Node
  attr_reader :data, :children
  attr_accessor :term
  def initialize(data)
    @data = data
    @children = []
    @term = false
  end

  def insert(char)
    return get(char) if have?(char)

    child = Node.new(char)
    @children << child
    child
  end

  def have?(char)
    @children.each do |c|
      return true if c.data == char
    end

    false
  end

  def get(char)
    @children.each do |child|
      return child if child.data == char
    end

    false
  end
end

class Trie
  attr_reader :root
  def initialize
    @root = Node.new(nil)
  end

  def insert(word)
    node = @root
    word.size.times do |i|
      child = node.insert(word[i])
      node = child
    end
    node.term = true
  end

  def have?(word)
    node = @root
    word.size.times do |i|
      return false unless node.have?(word[i])
      node = node.get(word[i])
    end

    return node.term == true
  end
end

trie_spec.rb

require_relative "../lib/trie"

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

    its(:data) { should == 'a' }
    its(:children) { should == [] }

  end

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

    subject { @node }

    its(:data) { should == 'a' }
    it { should be_have('b') }
    it { should_not be_have('c') }
  end
end

describe Trie do
  context 'inserted word "ab"' do
    before do
      @trie = Trie.new
      @trie.insert("ab")
    end

    subject { @trie }

    its(:root) { should be_have('a') }
    it { should be_have('ab') }
    it { should_not be_have('ac') }
  end

  context 'inserted word "abcd", "abcdefg" and "12345"' do
    before do
      @trie = Trie.new
      @trie.insert("abcd")
      @trie.insert("abcdefg")
      @trie.insert("12345")
    end

    subject { @trie }

    its(:root) { should be_have('a') }
    its(:root) { should be_have('1') }
    its(:root) { should_not be_have('b') }
    it { should be_have("abcd") }
    it { should be_have("abcdefg") }
    it { should be_have("12345") }
    it { should_not be_have("123") }
    it { should_not be_have("abc") }
  end
end