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!”….?

This….THIS is the energy.

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.

Not those kinds of 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. :)