Binary Search Tree: Part2, The Code

Binary search algorithm

Today’s post is a follow-on from the original Part 1, an introduction to Binary Search Tree. For the sake of simplicity and coherency I will use the same values in the nodes. As a different means to writing out content in a blog post, I’ve chosen to use RSpec to communicate intent and elaborate on the code as a form of self-blog. 

So to kick off, I will present the actual code for the Binary Search Tree, supporting only two main sets of functionality, insertion and search. Thereafter, the spec file.

# Kudos to Phil McClure (rubyalgorithms.com)

module Trees
  class BinarySearchTree
    attr_reader :root

    class Node
      attr_reader :parent, :left, :right

      def initialize(value)
        @parent = value
        @left = nil
        @right = nil
      end

      def insert(value)
        if value <= @parent
          @left.nil? ? @left = Node.new(value) : @left.insert(value)
        elsif value > @parent
          @right.nil? ? @right = Node.new(value) : @right.insert(value)
        end
      end
    end

    def insert(value)
      if @root.nil?
        @root = Node.new(value)
      else
        @root.insert(value)
      end
    end

    def search(value, node=@root)
      return nil if node.nil?
      if value < node.parent
        search(value, node.left)
      elsif value > node.parent
        search(value, node.right)
      else
        return node
      end
    end

    def initialize
      @root = nil
    end
  end
end

And the spec file

describe Trees::BinarySearchTree do
  before :each do
    @bst = Trees::BinarySearchTree.new
  end

  context 'During initialization' do
    it 'should initialize with a nil root value' do
      expect(@bst.root).to eq nil
    end
  end

  context 'Interface' do
    it 'should allow a new value to be inserted as a node' do
      @bst.insert(15)
      @bst.insert(10)
      bottom_left_of_root = @bst.root.left
      expect(bottom_left_of_root.parent).to eq 10
      expect(bottom_left_of_root.left).to be nil
      expect(bottom_left_of_root.right).to be nil
    end

    it 'should add values less than parent to the left as nodes' do
      @bst.insert(15)
      @bst.insert(10)
      bottom_left_of_root = @bst.root.left
      expect(bottom_left_of_root.parent).to eq 10
      expect(bottom_left_of_root.left).to be nil
      expect(bottom_left_of_root.right).to be nil
    end

    it 'should add values greater than parent to the right as nodes' do
      @bst.insert(15)
      @bst.insert(20)
      bottom_right_of_root = @bst.root.right
      expect(bottom_right_of_root.parent).to eq 20
      expect(bottom_right_of_root.left).to be nil
      expect(bottom_right_of_root.right).to be nil
    end
  end

  context 'Inserting' do
    it 'should assign first value to root, if root is nil' do
      @bst.insert(1)
      expect(@bst.root.parent).to eq 1
    end

    it 'should build a binary search tree' do
      @bst.insert(15)
      @bst.insert(10)
      @bst.insert(8)
      @bst.insert(12)
      @bst.insert(20)
      @bst.insert(17)
      @bst.insert(25)
      expect(@bst.root.left.left.parent).to eq 8
      expect(@bst.root.left.right.parent).to eq 12
      expect(@bst.root.right.left.parent).to eq 17
      expect(@bst.root.right.right.parent).to eq 25
    end
  end

  context 'Search' do
    it 'should traverse the tree and find a matching leaf on the right' do
      @bst.insert(15)
      @bst.insert(10)
      @bst.insert(8)
      @bst.insert(12)
      @bst.insert(20)
      @bst.insert(17)
      @bst.insert(25)
      expect(@bst.search(17).parent).to eq 17
    end

    it 'should traverse the tree and find a matching leaf on the left' do
      @bst.insert(15)
      @bst.insert(10)
      @bst.insert(8)
      @bst.insert(12)
      @bst.insert(20)
      @bst.insert(17)
      @bst.insert(25)
      expect(@bst.search(12).parent).to eq 12
    end

    it 'should traverse the tree and find the root node if it is the search value' do
      @bst.insert(15)
      @bst.insert(10)
      @bst.insert(8)
      @bst.insert(12)
      @bst.insert(20)
      @bst.insert(17)
      @bst.insert(25)
      expect(@bst.search(15).parent).to eq 15
    end
  end
end

2 comments

Leave a Reply

Your email address will not be published. Required fields are marked *