Kata: Binary Search Tree in Ruby

Yesterday in the Barcelona Software Craftsmanship coding dojo we did the Binary Search Tree kata.

Raúl Lorca and I paired using TDD in C# to get to a pretty OO solution.

We didn't finish the exercise. We got to create the binary search tree but we didn't have time to code the in-order depth-first traversal.

Well, it doesn't matter. The important thing is that we practiced TDD, recursion and OO by test-driving a recursive data structure.

Today, with a bit more of time, I did the the whole kata in Ruby.

These are the resulting tests, after deleting some I used as scaffolding to get to the final version of the code (check the commits if you want to see the evolution of the tests):

	require './binary_search_tree'
	describe BinarySearchTree do
	it "creates a tree without any sons" do
	tree = BinarySearchTree.new(3)
	expect(tree.in_order()).to eq [3]
	end
	it "creates a tree with left and right sons" do
	tree = BinarySearchTree.new(2)
	tree.insert(5)
	tree.insert(1)
	expect(tree.in_order()).to eq [1, 2, 5]
	end
	it "creates a complex tree inserting values one by one" do
	tree = BinarySearchTree.new(4)
	tree.insert(6)
	tree.insert(5)
	tree.insert(8)
	tree.insert(2)
	tree.insert(3)
	tree.insert(1)
	expect(tree.in_order()).to eq [1, 2, 3, 4, 5, 6, 8]
	end
	it "creates a complex tree from a list" do
	tree = BinarySearchTree.create_from_list([4, 6, 5, 8, 2, 3, 1])
	expect(tree.in_order()).to eq [1, 2, 3, 4, 5, 6, 8]
	end
	end

view raw binary_search_tree_spec.rb hosted with ❤ by GitHub

And this is the final version of the code:

	class BinarySearchTree
	def initialize(value)
	@value = value
	end
	def insert(new_value)
	if new_value < value
	self.left_tree = add_value_at(left_tree, new_value)
	else
	self.right_tree = add_value_at(right_tree, new_value)
	end
	end
	def self.create_from_list(numbers)
	tree = BinarySearchTree.new(numbers.first)
	numbers.drop(1).reduce(tree) do |tree, value|
	tree.insert(value)
	tree
	end
	end
	def in_order()
	sorted_list = tree_in_order left_tree
	sorted_list.push(value)
	sorted_list.concat(tree_in_order right_tree)
	end
	private
	attr_accessor :left_tree, :right_tree
	attr_reader :value
	def tree_in_order tree
	if tree
	tree.in_order()
	else
	[]
	end
	end
	def add_value_at(tree, new_value)
	if tree
	tree.insert(new_value)
	tree
	else
	BinarySearchTree.new(new_value)
	end
	end
	end

view raw binary_search_tree.rb hosted with ❤ by GitHub

To document the whole TDD process I committed the code after every passing test and every refactoring.

You can check the commits step by step here and all the code in this repository in GitHub.

I had done the same exercise in Clojure several weeks ago as part of the Exercism problems. Compare the code there with this one if you like.