Browsed by
Tag: BinaryTreeSort

Using TDD to solve algorithms, Part I

Using TDD to solve algorithms, Part I

When I started a Rails bootcamp through the Firehose Project, I liked the idea of test driven development but it took a while to slowly appreciate its importance. Working on a collaborative group project we all got into the habit of writing code, then going back and writing obligatory tests to show that it worked. It didn’t take long, as code changed, for errors to start popping up though our tests were still passing. We quickly realized that 1 – our tests weren’t always testing exactly what we thought they were and 2 – we hadn’t been testing enough cases. Testing quickly moved up in priority on our project!

However, it was after a chat with an acquaintance who works in the industry that I decided to try using TDD to actually drive development. I was working on a sorting algorithm using a binary tree and the pattern wasn’t jumping out at me as some of the others had. OK, let’s put TDD to work.

The problem

A binary tree is a data structure that consists of nodes with each node having at most 2 child nodes. An example is given below.

binary-tree

# 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

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
end

We needed to write an algorithm to take an array of integers and return the sorted array. I realized the problem needed to be broken into two parts – turning an integer array into a sorted binary tree and turning the tree back into an array. The second problem is easier, so let’s tackle that first.

Turning a btree into an array

We want to convert the binary tree into an array from left to right. The tree above should return [4, 2, 5, 1, 3, 6, 7]. Let’s set up an instance method called to_a and a simple test to go with it

# binary_tree_sort.rb
  def to_a
  end

# binary_tree_sort_test.rb
  test 'Should return array from tree'
    assert_equal [7], @seven.to_a
  end

Running

ruby binary_tree_sort.rb

from the terminal shows us a failing test of course. The next step is to write the SIMPLEST code that will pass the test. At this step it seems a bit silly, but it sets up the pattern for TDD. Modify our method to return 7.

# binary_tree_sort.rb
  def to_a
    [7]
  end

This gives us a passing test. Ok, let’s add another assertion to our test.

# binary_tree_sort_test.rb
    assert_equal [5], @five.to_a

Again, we have a failing test. Fixing it is very simple as we recognize that in each case we are returning the payload attribute.

# binary_tree_sort.rb
  def to_a
    [payload]
  end

Passing, again. We can add an assertion for our other childless node if we want to assure ourselves that the method will still work and we can convince ourselves that this method will work for any childless node. Now let’s add an assertion for a node with a child.

# binary_tree_sort_test.rb
    assert_equal [6, 7], @six.to_a

Once again, we have a failing test. In order to get this to pass we’ll need to add right into our array – but adding right into our array would fail the previous tests, so it needs to be conditional.

# binary_tree_sort.rb
  def to_a
    if right.nil?
      return [payload]
    else
      return [payload, right.payload]
    end
  end

This passes our test but it sure doesn’t look clean or repeatable. Let’s add another failing assertion to see where it takes us.

# binary_tree_sort_test.rb
    assert_equal [3, 6, 7], @three.to_a

Now, we will need more complex code, because this example wants a return value of

    [payload, right.payload, right.right.payload]

which tells us that a recursive function is definitely a good way to go. We quickly realize that right.payload is just right.to_a. Let’s try a recursive function.

# binary_tree_sort.rb
  def to_a
    return [payload] + right.to_a
  end

It worked! Try adding a new assertion

# binary_tree_sort_test.rb
    assert_equal [4, 2, 5], @two.to_a

and we find that it fails again, of course, because we’ve only given the right side of the tree. We can fill in the left side to get our test to pass. Then, check that the method passes our remaining assertion.

# binary_tree_sort.rb
  def to_a
    return left.to_a + [payload] + right.to_a
  end

# binary_tree_sort_test.rb
    assert_equal [4, 2, 5, 1, 3, 6, 7], @trunk.to_a

In part II I’ll cover using TDD to create the sorting algorithm.