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