Using TDD to solve algorithms, Part III
After Part I and Part II we were left with the following code and a failing test – our binary tree placed 7 at the trunk, 14 on the right node then 15 in place of the 14. We need the tree to place the 15 as the right node of the 14 node. We had decided that the best way to do this was to create a separate function for adding nodes which I’ve included as add_node.
# binary_tree_sort.rb require_relative 'binary_tree_sort_test' class BinaryTree attr_accessor :payload, :left, :right def initialize(payload, left, right) @payload = payload @left = left @right = right end def to_a return left.to_a + [payload] + right.to_a end def add_node(value) end def self.sort(ary) return nil if ary.nil? btree = BinaryTree.new(ary.shift, nil, nil) until ary.count == 0 if ary[0] > btree.payload btree.right = BinaryTree.new(ary.shift, nil, nil) else btree.left = BinaryTree.new(ary.shift, nil, nil) end end return btree.to_a end # binary_tree_sort_test.rb require 'minitest/autorun' class Tester < Minitest::Unit::TestCase def setup @seven = BinaryTree.new(7, nil, nil) @five = BinaryTree.new(5, nil, nil) @four = BinaryTree.new(4, nil, nil) @six = BinaryTree.new(6, nil, @seven) @three = BinaryTree.new(3, nil, @six) @two = BinaryTree.new(2, @four, @five) @trunk = BinaryTree.new(1, @two, @three) end def test_btree_to_array assert_equal [7], @seven.to_a assert_equal [5], @five.to_a assert_equal [4], @four.to_a assert_equal [6, 7], @six.to_a assert_equal [3, 6, 7], @three.to_a assert_equal [4, 2, 5], @two.to_a assert_equal [4, 2, 5, 1, 3, 6, 7], @trunk.to_a end def test_btree_nil assert_equal nil, BinaryTree.sort(nil) end def test_btree_sort_ary_n_1 assert_equal [1], BinaryTree.sort([1]) assert_equal [7], BinaryTree.sort([7]) end def test_btree_sort_ary_n_2 assert_equal [1, 7], BinaryTree.sort([1, 7]) assert_equal [1, 7], BinaryTree.sort([7, 1]) assert_equal [6, 6], BinaryTree.sort([6, 6]) assert_equal [-5, 0], BinaryTree.sort([0, -5]) end def test_btree_sort_ary_n_3 assert_equal [4, 7, 15], BinaryTree.sort([7, 4, 15]) assert_equal [7, 14, 15], BinaryTree.sort([7, 14, 15]) end end
Refactoring with the new method, but no change in functionality gives us
# binary_tree_sort.rb def add_node(new_value) if new_value > self.payload self.right = BinaryTree.new(new_value, nil, nil) else self.left = BinaryTree.new(new_value, nil, nil) end end def self.sort(ary) return nil if ary.nil? btree = BinaryTree.new(ary.shift, nil, nil) until ary.count == 0 btree.add_node(ary.shift) end return btree.to_a end
Sure enough, we get the same failing test as before. We are going to need to go deeper into the btree. It makes sense to define a pointer that refers to the current node and a boolean flag to let us know when we’ve finally placed the node. We know that we should place the new value only into a nil branch, so we’ll check for that.
# binary_tree_sort.rb def add_node(new_value) placed = false current_node = self until placed if new_value > current_node.payload if current_node.right.nil? current_node.right = BinaryTree.new(new_value, nil, nil) placed = true end else if current_node.left.nil? current_node.left = BinaryTree.new(new_value, nil, nil) placed = true end end end end
Instead of failing tests, this hangs our program in an infinite loop as there are cases where placed is never set to true. Something has to happen when we can’t place the value and that, of course is that we set the current_node to move down the tree to the branch we just checked.
# binary_tree_sort.rb def add_node(new_value) placed = false current_node = self until placed if new_value > current_node.payload if current_node.right.nil? current_node.right = BinaryTree.new(new_value, nil, nil) placed = true else current_node = current_node.right end else if current_node.left.nil? current_node.left = BinaryTree.new(new_value, nil, nil) placed = true else current_node = current_node.left end end end end
This code passes our tests and further testing fails to break it. This is our binary tree sort.