Toy Problem Time: Tree Count Leaves

Hey there friends and fellow developers! Today I am going to be telling you about a fun toy problem, Tree Count Leaves. This fun little brain teaser is a good introduction to recursion. In order to start this problem, you should first at least understand a little bit about how a tree works. Anyway, the problem is presented as follows.

Implement a countLeaves method on this Tree class. 
A leaf node is any node in the tree that has no children.
countLeaves should traverse the tree, and return the number of leaf nodes the tree contains.

Inputs:
None

Outputs:
A number.

Edge Cases:
None.

Constraints:
None.

The goal is to be able to implement a function that will count every leaf node. A leaf node is a node that does not contain any children.

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

/**
 * Returns the number of amount of leaves a tree has.
 */
Tree.prototype.countLeaves = function() {
  // TODO: Your code here!

};

/**
 * Add an immediate child
 * (wrap values in Tree nodes if they're not already)
 */
Tree.prototype.addChild = function(child) {
  if (!child || !(child instanceof Tree)) {
    child = new Tree(child);
  }

  if (!this.isDescendant(child)) {
    this.children.push(child);
  } else {
    throw new Error('That child is already a child of this tree');
  }

  // return the new child node for convenience
  return child;
};

/**
 * Check to see if the provided tree is a child of this tree or any of its sub trees
 */
Tree.prototype.isDescendant = function(child) {
  const childIndex = this.children.indexOf(child);

  if (childIndex !== -1) {
    // `child` is an immediate child of this tree
    return true;
  }

  return !!this.children.find(child => child.isDescendant(child));
};

/**
 * Remove an immediate child
 */
Tree.prototype.removeChild = function(child) {
  const childIndex = this.children.indexOf(child);

  if (childIndex === -1) {
    throw new Error('That node is not an immediate child of this tree');
  }

  this.children.splice(childIndex, 1);
};

Now where do we start? Given that we already know how a tree works, we know we need to recursively pass over each child node in the tree and check to see if any of those child nodes have any children. We know that we must start with a base case, given that we also know we must use recursion.

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

Tree.prototype.countLeaves = function() {
  // TODO: Your code here!
  //create counter to keep track of the number of leaves. 
  let leafCount = 0;

  //if tree does not contain children, then we must increase counter.
  if(this.children.length === 0){
    count++;
  }


  //recursive case
};

Tree.prototype.addChild = function(child) { ... };
Tree.prototype.isDescendant = function(child) { ... };
Tree.prototype.removeChild = function(child) { ... };

So here we have a bit of pseudo-code and a base case to get started. Now this would work if our root node does not have any children at all, but what if we had tens or maybe hundreds of nodes in the tree, we would need to use recursion to do that!

Tree.prototype.countLeaves = function() {
  // TODO: Your code here!
  //create counter to keep track of the number of leaves. 
  let leafCount = 0;

  //if tree does not contain children, then we must increase counter.
  if(this.children.length === 0){
    count++;
  }


  //recursive case
  this.children.forEach(child =>{
    count += child.countLeaves();
  });

  return count;
};

Coolio! So here we now have both our recursive and our base case. Using recursion we run through the tree and increase the count every time we get to a leaf node. Because we are using recursion, we must add the call of the function to the count every time it passes through so that count will be saved from the return of said function.

And that's all there is to it. I hope you enjoyed my bad explanations of how recursion works. Thank you so much for reading. Happy coding, hackers!