CoDEVIANT #24 — Apples Falling from the Binary Tree

You know what they say about apples: that they don’t fall far from the tree. Today’s problem is about finding the depth of a tree. What does this mean? Well, it means we are going to count the number of links it takes to get to a given node from the root. Then we add all of those numbers together to calculate the “depth”.

Consider this crudely drawn tree. Each red arc that ends on a node signifies a measurement of depth. Focusing on just the left side of the tree starting from the root, we go down to the Node with the value of 3 and say the trip there was a depth of one. Now from the root to Node-3-Left to Node-4-Left, that’s a depth of 2. We add those up, we get 3. Now also, add up root to Node-3-Left to Node-2-Left-But-Slanted-To-The-Right, now we get 5. If we continued like this for the entire tree, we’d end up with a depth of 10.

I like to think of this problem with apples…

Mmmm…sweet, candy red apples…

So why apples? Well, in my mind this reminds me picking up fruits in a magical orchard. The farmer stands at the top of their orchard and says

“If I go down a pace to either the left or right side, I know I’m going to find one apple if there’s a harvest going on there. I also know that if I go further down to either the left or right side, I’m going to find two apples. Now if those trees that had two apples have a path leading to another apple tree further down the road, I know I’m going to see a tree that will give me three apples!”

You can visit any apple-tree (node), as often as you like, but you can’t pick up an apple that is already retrieved.

Think of the stars as apples (because I can barely draw in real life and MS Paint is)…

So the big question for the day is: H̶o̶w̶ ̶d̶o̶ ̶w̶e̶ ̶g̶e̶t̶ ̶t̶h̶e̶ ̶d̶e̶p̶t̶h̶ ̶o̶f̶ ̶t̶h̶e̶ ̶b̶i̶n̶a̶r̶y̶ ̶t̶r̶e̶e̶?

How do we get those delicious apples from the orchard?

Well here is the answer to that:

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
function nodeDepths(root) {
 let depthCount = 0
 return helper(root, depthCount)
 }
function helper(node, counter) {
  if(!node) {
    return 0
  }
  let numbah = counter +  helper(node.right, counter + 1)  +       helper(node.left, counter + 1)
  return numbah
}

First up, we define our BinaryTree class. Without it, everything falls apart because our computer won’t know how our nodes (apple trees) are made.

class BinaryTree {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

Next, we have our function nodeDepths which has an argument of the root of our binary tree.

function nodeDepths(root) {
  let depthCount = 0
  return helper(root, depthCount)
}

We create a variable, depthCount, initialized at zero since we’re starting at the root. Then we return the result of a call to a new method helper which takes the root and the depthCount variable we just created as arguments. Nothing much seems to be going on, but that’s because the helper method is doing all the heavy lifting.

Speaking of helper:

function helper(node, counter) {
  if(!node) {
    return 0
  }
let numbah = counter +  helper(node.right, counter + 1)  +       helper(node.left, counter + 1)
  return numbah
}

So when the previous method calls helper we check to see if the node that is passed in has any substance to it, either a value, left, right property. If it does not, then it returns zero.

However, if this is not the case we say create a variable called numbah. numbah will equal the counter argument that was passed in PLUS the result of calling the function we’re currently running on the node’s right child, while passing the counter + 1 as the counter argument PLUS the exact same as the last chunk, except with the node’s left child.

Then we return numbah.

Yay recursion!

By lopping off the teeth of the helper method by checking if the node exists and returning 0 if that’s the case, we allow this method to recursively travel through the tree (orchard) and calculate how many steps it takes to get from the root to the current node (pick the apples at each node) and then return them ultimately to the first declaration of the numbah variable. So once a millisecond or so goes by, all of the repetitive calls of the helper method will have resolved. The nodes that would have artificially inflated our count of apples are weeded out, giving us just how many apples we were able to pick in the orchard (an accurate calculation of the tree’s depth).

Anyways, that’s a wrap for today. I have some other projects to work on and I need to get groceries, although I sprained my back so maybe I’ll have those delivered. Have a good one!

How’d you like dem apples?