# CoDEVIANT #23 — Tree Hee Hee

--

So remember about a month ago when I said “I’m going to do my best to make writing these a daily thing!”….?

Well, life got in the way. I had a slew of interviews, none of which I got the job for.

And I’ve been working on some side projects and recovering from the run-up to election week…then election week itself.

Anyways, I’ve been getting back to my data-structure studies and I have learned a great deal more about graphs, stacks, queues, hash-tables, and trees.

So I come to you today with what a lot of leet devs would consider a really easy problem. The thing is I’ve never worked on this algorithm, and I just wasn’t in touch with my star-player today. So I got frustrated right away and looked up the answer. After groking the code, however, I feel confident that I can explain what is going on. Hopefully I reinforce my understanding, you learn something new (or get reminded), and we fill up the screen with the most fire gifs.

So we have here a binary tree:

This is not a binary search tree, other wise it would be sorted in such a way that all nodes to the left of a given node would have a value smaller than that of its parent. For terminology’s sake:

- root: the top node of the tree
- leaf node: a node that has no children
- branch: the traversal from root to a leaf-node following a path of links between nodes

What we want to do is traverse down the tree branch by branch. For each node, you get the sum of the nodes visited during the traversal and place the final sum in an array.

For the above tree our final product would look something like this:

1–3–2–7: 13

1–3–2–3: 9

1–3–5–4: 13

1–3–5–9: 18

1–4–2–3: 10

1–4–2–4: 11

1–4–6–8: 19

1–4–6–9: 20

Which would give us an array that looks like this:

[13, 9, 13, 18, 10, 11, 19, 20]

Here is the answer:

class BinaryTree {

constructor(value) {

this.value = value;

this.left = null;

this.right = null;

}

}function branchSums(root) {

let answer = []

helper(root, 0, answer)

return answer

}function helper(node, currentSum, array) {

if(!node) {

return

}

const val = currentSum + node.value

if(!node.left && !node.right) {

array.push(val);

return;

}

helper(node.left, val, array)

helper(node.right, val, array)

}

Okay, so there’s quite a bit going on.

First, we create the class for our BinaryTree:

`class BinaryTree {`

constructor(value) {

this.value = value

this.left = null

this.right = null

}

}

Next we have our *branchSums* method.

`function branchSums(root) {`

let answer = []

helper(root, 0, answer)

return answer

}

This doesn’t seem altogether too exciting. We just:

- define an empty array,
*answer* - call some method named
*helper*and pass in the**root**, the number zero, and the*answer*array we just defined. - we return
*answer*

So all of this begs the question. What the hell is in *helper* and what’s so special about it? Well let’s first take a look at it.

function helper(node, currentSum, array){

if(!node) {

return

} const value = currentSum + node.value

if(!node.left && !node.right) {

array.push(value)

return

} helper(node.left, val, array)

helper(node.right, val, array)

}

So real quick and dirty:

- We call
*helper*and pass in the root, 0, and*answer*for the arguments node, currentSum, array (respectively) - Once inside the machinations of the
*helper*method we check to see if the node exists. If it does not, then we return. - So if the node
**does**exist, then we create a variable called**value**and we make it equal the currentSum (on the first pass its 0) plus*node.value*. ***If we’re using the binary tree illustration from earlier in this article it’s going to be 1*** - Next we make sure that we have children nodes that regards the current node as their parent. If this is not the case, we push
**value**into the*array*and return - However, if this node does have children, then we call
*helper*and pass in the left and right child in the first argument slot.**value**will be the 2nd argument, and*array*will be the third.

This answer uses recursion, which is recalling instructions to perform code repetitively until a certain condition is met. For our condition, it’s literally that we run out of nodes to check due to a lack of children nodes — that means we will have hit the leaf nodes.

So if we think of this answer with the binary tree I illustrated in mind, our first cycle for the *helper *method will be:

- Adding 0 and 1 (the root node’s value)
- Calling itself on the node’s left child — and technically waiting for that to resolve itself (which will take the blink of an eye). This is where the method will be calculating the following before pushing them into our
*answer*array and then returning that:

1–3–2–7: 13

1–3–2–3: 9

1–3–5–4: 13

1–3–5–9: 18 - Calling itself on the node’s right child — you know the drill:

1–4–2–3: 10

1–4–2–4: 11

1–4–6–8: 19

1–4–6–9: 20

So with these sums passed into the *array*, it becomes *answer* and that’s what we return. :)