Using TDD to solve algorithms, Part III

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.

Refactoring with the new method, but no change in functionality gives us

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.

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.

This code passes our tests and further testing fails to break it. This is our binary tree sort.


2 thoughts on “Using TDD to solve algorithms, Part III

  1. So what do you think? Can TDD result in the emergence of an algorithm to solve something like this? Or do we have to wrap our minds around a problem before we can solve it?

    1. I think a little bit of each. For this problem, I definitely felt that TDD helped the emergence of the algorithm. Once I started to iterate on more complex tests an evident pattern emerged that I wasn’t seeing beforehand.

Comments are closed.

Comments are closed.