We haven't really sold recursion as a concept at this point. We kind of get it, but are probably not convinced why good old while or for loops can't be used in its place. Recursion shines when it solves problems that look like a reoccurring pattern. An example of that is a tree. A tree has some similar concepts to it such as consisting of nodes. A node without children connected to it is called a leaf. A node with children but that has no connection to an upward node is called a root node. Let's illustrate this with a diagram:

There are a few interesting operations that we would want to carry out on a tree:

• Summarise the node values
• Count the number of nodes
• Calculate the width
• Calculate the depth

To attempt to solve that, we need to think about how to store a tree as a data structure. The most common way of modeling it is by creating a representation of a node as having a value, and a left property and a right property, then both those properties point to nodes in turn. Therefore, the code for said Node class might look like this:

class NodeClass {
  constructor(left, right, value) {
    this.left = left;
    this.right = right;
    this.value = value;
  }
}

The next step is thinking how to create the tree itself. This code shows how we can create a tree with a root node and two children, and how to bind these together:

// tree.js

class NodeClass {
  constructor(left, right, value) {
    this.left = left;
    this.right = right;
    this.value = value;
  }
}

const leftLeftLeftChild = new NodeClass(null, null, 7);
const leftLeftChild = new NodeClass(leftLeftLeftChild, null, 1);
const leftRightChild = new NodeClass(null, null, 2);
const rightLeftChild = new NodeClass(null, null, 4);
const rightRightChild = new NodeClass(null, null, 2);
const left = new NodeClass(leftLeftChild, leftRightChild, 3);
const right = new NodeClass(rightLeftChild, rightRightChild, 5);
const root = new NodeClass(left, right, 2);

module.exports = root;

Worth highlighting is how the instances left and right do not have children. We can see that because we set their values to null on creation. Our root node, on the other hand, has  the object instances left and right as children.