Thoughtful algorithm methodology

Title

If you’re a software developer,

you’ve likely come across a technical problem—either in an interview or developing your product—for which you couldn’t immediately intuit a solution. When this happens, most people do one of the following:

  1. Start writing code frantically, trusting that they can sling together a squirrelly solution
  2. Stare blankly at their screen, waiting for divine intervention or a stroke of brilliance, or both

If either of these statements hits a little too close to home, this article is for you.

We improve as developers over time and through practice. We get progressively better at recognizing patterns and applying familiar solutions, but in the process, we are less frequently challenged by problems that are truly alien, and for which we feel completely unprepared. Solving these problems requires a different approach than that associated with pattern recognition and code reproduction, and it's deserving of its own explicit methodology.

This article isn’t about algorithm design—it instead describes a methodology for reasoning through unfamiliar problems and developing solutions. I introduce this process with an example of JavaScript algorithm development, but it can be abstracted to any form of logic-based decision-making.

So! Let’s say that we have a tree data structure, and we want to count its leaves. The tree itself is comprised of branches which are themselves tree nodes. This can be hard to visualize, but it’s kind of like broccoli: if you look at a head of broccoli closely, you’ll see that each floret looks itself like a little head of broccoli.

Uh, right. Anyway, a leaf node is any node in the tree that has no children—no little trees that branch off from itself. Here’s an illustration of a tree with three leaves:

      * <- root
     / \
    *   * <- leaf
   / \
  *   * <- leaf
 /
* <- leaf

Our code should traverse the tree, and return the number of leaf nodes the tree contains.

Instead of tensing up or typing out hurried for-loops, I find it helpful to reason through the problem using a sequence of steps:


1. Understand the interface

The key questions to ask here are:

  1. What information are we getting in?
  2. What do we expect the program to return?

In this case, we have a tree constructor:

var Tree = function(value){
    this.value = value;
    this.children = [];
};

We want to give each tree we construct a method that counts its leaves:

Tree.prototype.countLeaves = function() {};

This method will work on the tree itself, and output a number—the number of leaves the tree contains.

So if we call the following sequence of commands…

var root = new Tree();
root.countLeaves();  // we now have one leaf
root.addChild(new Tree());  // a method that adds children
root.countLeaves();  // still one leaf
root.addChild(new Tree());
root.children[0].addChild(new Tree());
root.children[0].addChild(new Tree());
root.children[0].children[0].addChild(new Tree());
root.countLeaves();  // our function should return 3

We expect the output of our countLeaves function to be the number 3. Great! But how can we check our outputs against the expected results?


2. If you’re using test-driven-development, write a test to verify your solution

This is a helpful step because it forces us to take a vague sense of what our program may need to output and express it concretely.

I won’t spend much time describing the testing process because there are far better, language-and frame-work specific guides elsewhere online. But if we were writing this algorithm with JavaScript and using Mocha, we might call the commands we outlined in Step 1 and then write the following test:

describe(‘root.countLeaves()’, function() {
    it(‘should solve for a case where the tree has three leaves’, function() {
        expect(root.countLeaves()).to.equal(3);
    });
});

If you aren’t familiar with test-driven development, don’t worry. You can use Node or the Chrome console to construct a tree and test out your countLeaves function in real-time.


3. Explore the problem space and identify relevant patterns and techniques

Our tree is comprised of child nodes, each of which could be either a tree itself (meaning that it has children), or a leaf (meaning that it does not have children). When we consider the root tree, we need to count its children. If it has none, it’s a leaf! It it has one child or more, we need to consider each one in turn. In fact, the process is the same regardless of which node we’re on: does it have children? If no, it’s a leaf. If yes, move on to each of its children.

This problem is comprised of smaller instances of the same problem. Does that sound familiar? Yep, it’s a perfect opportunity to use a recursive function. We don’t need to write out that function right now, but just knowing that we’ll use recursion will help us as we begin to consider our specific code.


4. Generate a simple plan to solve the problem

At this point, we should be able to express a solution in plain English. It can be helpful to take a moment and actually talk through our approach aloud, before we even begin typing anything:

For our leaf-counting algorithm, we’ll need to keep track of how many leaves we have. We’ll create a recursive, leafCount function that will take in a tree node. If the node doesn’t have any children, it’s a leaf, so well add one to our leaf count. If it does have children, we’ll call our leafCount function on each of them. Finally, we’ll return our finished count.

That wasn’t so bad, huh?


5. Write out your solution in pseudocode

Next, we’ll spell out our English-language solution in explicit steps, expressed in comments rather than actual code. This translates our abstract solution into a specific, line-by-line recipe. We do this rather than jump directly into writing code because doing so makes it easier to keep track of our thought-process if we get lost. Spell it out in pseudocode, and then work through the actual code later.

Tree.prototype.countLeaves = function () {
    // establish a count variable

    // create leafCount, a recursive function that evaluates a tree or sub-tree
        // if the tree doesn't have children
            // add 1 to the count variable
        // if it does have children
            // call leafCount on each child

    // call leafCount on the initial tree object
    // return the count
}

6. Translate each step into a line of code

Finally, it’s time to write some code. Oh man. But rather than a vague sense of the solution and a more concrete, visceral sense of frustration, we’re faced with a pleasant little pseudocode outline of the problem—the fruits of our labor so far. Here, our task shifts from logic to syntax: we just have to plug in the right JavaScript, and we’re good to go. We’ll add the actual code below its corresponding pseudocode:

Tree.prototype.countLeaves = function () {
    // establish a count variable
    var count = 0;

    // create leafCount, a recursive function that evaluates a tree or sub-tree
    var leafCount = function(tree) {
        // if the tree doesn't have children
        if (!tree.children.length) {
            // add 1 to the count variable
            return count++;
        // if it does have children
        } else {
            // call leafCount on each child
            for (var i = 0; i < tree.children.length; i ++) {
                leafCount(tree.children[i]);
            }
        }
     }

     // call leafCount on the initial tree object
     leafCount(this);
     // return the count
     return count;
}

We’ll run the method to check that it works, and because this code was written in the magical, faultless universe of my blog rather than the real world, it does:

root.countLeaves(); // evaluates to 3 (we're so smart/pretty)

This methodology has improved my algorithm design more than any module or library could. I’m confident that if you apply it to your own decision-making processes—development-related or otherwise—you’ll see similar results. Thanks for reading, and if you can come up with a cheeky acronym for these six steps, let me know…