Using TDD to solve algorithms, Part II

Using TDD to solve algorithms, Part II

In Part I, I went over using TDD to turn an existing binary tree into an ordered array of integers. Here in Part II we’ll use TDD to build a sorted binary tree from an unsorted array of integers. So, the entire flow will be [unsorted_integers] –> sorted_binary_tree –> [sorted_integers].

Since we’re starting with an array and ending with an array I didn’t see any need to create an instance of BinaryTree each time we use it. Instead I created a class method that will be called as

Let’s write a test as well as the method signature. Run the code and see a failing test.

Let’s return nil from our method to get a passing test.

We got an edge case out of the way. Let’s add another test.

Test fails. Modify to pass.

Pass. Again, we KNOW this is the wrong answer, but it’s the simplest answer to make our tests pass. Since we know it’s not the final goal we need to write another test.

Still passes. Time to make the test array bigger.

Passes again but we haven’t introduced the binary tree yet. Let’s do that and we’ll see that the code starts to get messier

This still passes but it’s not very pretty. We add another test.

And this, of course fails. The array wasn’t sorted.

Let’s add a conditional statement to our code to get the second integer onto the correct branch.

It passes again, but it’s really looking like a mess. However, we can see two things – 1. We are going to need a recursive function as we have btrees nested in btrees. 2. We are going to need a conditional statement to determine where to put child branches.
Let’s do some minor refactoring. I know the first item in the ary is going to be at the top of the btree and I know I won’t need it again. If I shift it off the array I can easily access the next item without indexing. Next, I recognize that as long as there are numbers left in my array I need to add a branch to the btree so I wrap the if/else/end statement in an unless ary.count == 0. I can then add the next integer as a btree node on the appropriate side using the left and right methods.

It passes. Let’s add more tests.

This still passes. We’re good on 2 integer arrays. Let’s try 3.

Fail. Of course, we’ve only set up our btree to add 2 branches. Change our unless statement to

to create a loop and our test passes. Add another test to try to break it with integers in a different order.

We have a failing test and can look through our method and see why. The 14 was placed on the right of the 7, then it was replaced with the 15. We need to go deeper to find the correct node. This method is starting to do a lot of things so it makes sense to create a new method with the sole responsibility of adding a node in the right place. From inside our unless loop we will call

In Part III we’ll factor out that method and finish up the algorithm. In the meantime, keep adding tests and making them to pass.

One thought on “Using TDD to solve algorithms, Part II

  1. In these three simple and beautifully written posts I learned a lot, about Algorithms, control flow and TDD.
    Thanks Aaron, can’t wait to read the next one!

Comments are closed.

Comments are closed.