# 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…

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!”

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**.

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!