Learning to think with recursion, part 2

Why should I care about this, anyway?

5 min readOct 21, 2016

In my last article, I discussed a particular strategy that I use when I am trying to design a recursive algorithm to solve a problem. I definitely recommend reading that article before this one, but to briefly summarize, here is the strategy:

Break the problem I am trying to solve down into a problem that is one step simpler
Assume that my function will work to solve the simpler problem — really believe it beyond any doubt
Ask myself: Since I know I can solve the simpler problem, how would I solve the more complex problem?

Last time, I applied this strategy in order to design a recursive algorithm that reverses a string. If you were reading that article and found yourself saying “What the feather! Why don’t you just use a loop to reverse the string? It’s so much simpler!” then I completely understand. That’s why, this time, we are going to apply this same strategy to do some neat things with recursive data structures.

Recursive Data Structures

Roughly speaking, a recursive data structure is a data structure that contains smaller versions of the same structure inside of itself. In Javascript, a basic example of a recursive data structure could be an object that contains other objects:

const danielKing= {
  name: {
    firstName: 'Daniel',
    lastName: 'King',
  },
  favorites: {
    foods: [
      'pizza',
      'curry'
    ]
  }
}

There are a number of recursive data structures that we use frequently in practice, but two of the most common are the linked list and the tree. In this article, I will be discussing one particular type of tree, called a binary search tree.

Binary Search Trees

Briefly, a binary search tree is a tree structure which satisfies two conditions:

Each node in the tree has two child nodes, which are called the “left” and “right” child nodes (one or both of the child nodes may be null).
The value of the left child node must be less than the value of the parent node, and the value of the right child node must be greater than the value of the parent node

A binary search tree is considered to be a recursive data structure because, if you look at only the left sub-tree of the top node, it is a whole binary search tree in and of itself. Similarly, if you look at only the right sub-tree, it is a complete binary search tree.

In Javascript, a definition for a single node of this tree might look like this:

function BinaryTreeNode(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

Notice that we are initializing the “left” and “right” properties of the BinaryTreeNode object to null, meaning that if we create a BinaryTreeNode, it is just a single node sitting by itself. In order to build up a proper binary tree, let’s add a method to this object type that will enable us to add a value to the tree:

function BinaryTreeNode(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}BinaryTreeNode.prototype.add = function(value) {
  // Do stuff to add another value to the tree
}

Once we have this function, we will be able to build up a complete binary tree simply by invoking this method repeatedly on the top node.

So, how can we write a method that will add a new value to the binary tree? Well, since a binary tree is a recursive data structure, let’s think about if we can write a recursive function to accomplish this task! We’ll apply the same strategy as before:

Break it down one level: I am trying to add a new value into the binary tree. A problem that is one step simpler would be to add a new value into the left or right sub-tree of the main tree, since those sub-trees are smaller than the main tree.
Leap of faith: I believe with every fiber of my being that my function can already add a new value into either the left or right sub-tree of the main tree.
Build it up: Since my function can add a new value into either the left or right sub-tree of the main tree, the only other thing I need to decide in order to be able to add the value to the whole tree is which sub-tree it the value should be added to. This goes back to the definition of a binary tree: If the new value is less than the value of the top node, then that value must go in the left sub-tree, but if it’s greater, it must go in the right sub-tree. If the appropriate subtree is null, then I can directly create a new node to fill the space, and if it is not null, I can recursively call the method again to add the value into the appropriate subtree.

If you want a challenge, try implementing this function before looking at the solution below:

function BinaryTreeNode(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}BinaryTreeNode.prototype.add = function(value) {
  if (value < this.value) {
    if (this.left === null) {
      this.left = new BinaryTreeNode(value)
    } else {
      this.left.add(value)
    }
  }  if (value > this.value) {
    if (this.right === null) {
      this.right = new BinaryTreeNode(value)
    } else {
      this.right.add(value)
    }
  }
}

Balanced Binary Trees

I hope you found this article to be informative! Stay tuned for part 3, in which we’ll discuss some practical applications of recursive data structures (ooooooh, ahhhhh!)

If you enjoyed this article or found it helpful, please click the heart below to recommend it to others who might like it as well!

Learning to think with recursion, part 2

Why should I care about this, anyway?

Recursive Data Structures

Binary Search Trees

Balanced Binary Trees

Written by Daniel King