TDD Kata (5): Tree Search

Some months ago, I read this message in a TDD list:
Implementation of game tree search using TDD
I read:
I am trying to use TDD to implement game tree searching but I am running into some issues.Using C#, MS Test and Rhino Mocks. My requirement is to traverse a tree to a specified depth and find the maximum value of the nodes at this depth. If a path ends before the specified depth then the value of the last node in the path should be considered. Sample usage looks like this: var depth = 5; var tree = new GameTree(); var treeSearch = new TreeSearch();var maxValue = treeSearch.FindMaxValue(tree, depth);

The first tests to implement:
* A search to depth zero should return the value of the root node * A search to depth one with no children should return the value of the root node * A search to depth one with one child should return the value of the child * A search to depth one with two children should return the highest value of the two children * A search to depth one of a tree with depth two should return the maximum value at depth one

All right, but:
Up to this point the tests are simple enough and mocking of the tree is simple. The last test starts driving towards a depth first tree traversal.Now I start on depth 2 tests which should drive the rest of the tree traversal algorithm: * A search to depth two should return the maximum value at depth two I decided to mock a complete binary tree with depth 2

The problem is the use of mocks: it complicates the solution. So, I started to solve the problem, without mocks, simply using a tree implementation to use as a base for other tests:

The solution is simple:

You can see the history of development at:

All tests are green:

Lesson learnt: some times (many times is easier to implement something concrete than build a mock. The tree I implemented could be refined, could be the base for an interface extraction, or could be implemented in other ways. But it served as a base for our search algorithm, using TDD.
Keep tuned!
Angel “Java” Lopez
- Full Post