Binary search tree without ruby magic

binary_search_tree_no_magic.rb

require 'rspec'

module BST
  class BSTNode
    attr_accessor :key, :left, :right

    def copy(other)
      @key = other.key
      @left = other.left
      @right = other.right
    end

    def has_children?
      not (@left.nil? || @right.nil?)
    end

    def add_children
      @left = BSTNode.new
      @right = BSTNode.new
    end

    def has_left_child?
      not @left.key.nil?
    end
  end

  class SearchTree
    def initialize
      @root_node = BSTNode.new

    end

    def insert(key)
      node = search_at(@root_node, key)
      node.key = key
      node.add_children unless node.has_children?
    end

    def search(key)
      search_at(@root_node, key)
    end

    def delete(key)
      node = search_at(@root_node, key)
      if node.has_left_child?
        swap_with_previous_node_and_remove(node)
      else
        node.copy(node.right)
      end

      nil
    end

    private

    def swap_with_previous_node_and_remove(node)
      previous_node = find_right_most_child(node.left)
      node.key = previous_node.key
      previous_node.copy(previous_node.left)
    end

    def search_at(search_node, key)
      return search_node if search_node.key.nil? || search_node.key == key

      if search_node.key < key
        search_at(search_node.right, key)
      else
        search_at(search_node.left, key)
      end
    end

    def find_right_most_child(node)
      return node if node.right.key.nil?
      find_right_most_child(node.right)
    end

  end
end

describe BST::SearchTree do
  describe '#insert' do

    it 'should return nil when the tree is empty' do
      expect(subject.search('key').key).to be_nil
    end

    it 'should return the root nodes value when we look it up' do
      subject.insert('key')
      expect(subject.search('key').key).to eq('key')
    end

    it 'should work with 3 values inserted in ascending order' do
      subject.insert(1)
      subject.insert(2)
      subject.insert(3)
      expect(subject.search(1).key).to eq(1)
      expect(subject.search(2).key).to eq(2)
      expect(subject.search(3).key).to eq(3)
    end

    it 'should work with 3 values inserted in descending order' do
      subject.insert(3)
      subject.insert(2)
      subject.insert(1)
      expect(subject.search(1).key).to eq(1)
      expect(subject.search(2).key).to eq(2)
      expect(subject.search(3).key).to eq(3)
    end
  end

  describe '#delete' do
    it 'should remove the single element' do
      subject.insert(1)
      subject.delete(1)
      expect(subject.search(1).key).to be_nil
    end

    it 'should remove a leaf node, but it should not remove the root' do
      subject.insert(1)
      subject.insert(2)

      subject.delete(2)

      expect(subject.search(1).key).to eq(1)
      expect(subject.search(2).key).to be_nil
    end

    it 'should remove non leaf element' do
      subject.insert(2)
      subject.insert(1)
      subject.insert(0)
      subject.insert(1.5)
      subject.insert(3)

      subject.delete(2)

      expect(subject.search(0).key).to eq(0)
      expect(subject.search(1).key).to eq(1)
      expect(subject.search(1.5).key).to eq(1.5)
      expect(subject.search(2).key).to be_nil
      expect(subject.search(3).key).to eq(3)

    end
  end
end