# #1 Branch Sums

###### tags:`Binary tree` `Easy`

## Problem
A branch sum is the sum of all values in a Binary Tree branch. A Binary Tree branch is a path of nodes in a tree that starts at the root node and ends at any leaf node.
Each `BinaryTree` node has an integer `value`, a `left` child node, and a `right` child node. Children nodes can either be `BinaryTree` nodes themselves or `None` / `null` .

### Sample Input

tree =    1
       /     \
      2       3
    /   \   /   \
   4    5  6     7
  / \  / 
 8  9 10

### Sample Output

[15, 16, 18, 10, 11]
// 15 == 1+2+4+8
// 16 == 1+2+4+9
// 18 == 1+2+5+10
// 10 == 1+3+6
// 11 == 1+3+7

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(n) space - where n is the number of nodes in the Binary Tree

:::

<br>

:::spoiler Hint 1
Try traversing the Binary Tree in a depth-first-search-like fashion.
:::

<br>

:::spoiler Hint 2
Recursively traverse the Binary Tree in a depth-first-search-like fashion, and pass a running sum of the values of every previously-visited node to each node that you're traversing.
:::

<br>

:::spoiler Hint 3
As you recursively traverse the tree, if you reach a leaf node (a node with no "left" or "right" Binary Tree nodes), add the relevant running sum that you've calculated to a list of sums (which you'll also have to pass to the recursive function). If you reach a node that isn't a leaf node, keep recursively traversing its children nodes, passing the correctly updated running sum to them.
:::

<br>

<hr/>

## Solutions

### Official

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

//O(n) time | O(n) space - where n is the number of nodes in the Binary Tree
function branchSums(root){
    const sums = [];
    calculateBranchSums(root, 0, sums);
    return sums;
}

function calculateBranchSums(node, runningSum, sums){
    if(!node) return;
    
    const newRunningSum = runningSum + node.value;
    if(!node.left && !node.right){
        sums.push(newRunningSum);
        return;
    }
    
    calculateBranchSums(node.left, newRunningSum, sums);
    calculateBranchSums(node.right, newRunningSum, sums);
}

<br>

---

### Everyone's

:::spoiler 東

Not a ideal solution. Storing each parent node value instead of accumulate current sum.

function branchSums(root) {
  const result = [];
  const branchNodeVals = [];
  function getSum(node){
    branchNodeVals.push(node.value);
    if(node.left) getSum(node.left);
    if(node.right) getSum(node.right);
    if(!node.left && !node.right){
      const branchSum = branchNodeVals.reduce((acc, cur) => acc + cur, 0);
      result.push(branchSum);
    }
    branchNodeVals.pop();
    return;
  }
  getSum(root);
  return result;
}

:::

<br>

:::spoiler Hao

- Similar to official solution except putting helper function inside
- Space complexity should be O(n)

/**
 * Time complexity: O(n) where n stands for numbers of nodes in the tree
 * Space complexity: O(m) where m stands for the deepest level of the tree
 */

function branchSums(root) {
  const res = [];
  const branchSumsInner = (node, acc) => {
    const newValue = acc + node.value;

    if (node.left === null && node.right === null) res.push(newValue);
    else {
      if (node.left !== null) branchSumsInner(node.left, newValue);
      if (node.right !== null) branchSumsInner(node.right, newValue);
    }
  };
  branchSumsInner(root, 0);
  return res;
}

:::

<br>

:::spoiler YC

Very similar to official solution

/*
  time: O(n) - where n is the number of nodes in the Tree
  space: O(n) - where n is the number of nodes in the Tree
*/


function branchSums(root) {
  let ans = [];
  add(root, ans, 0);
  return ans;
}

function add(node, ans, sum){
  if(!node) return;
  
  const newSum = sum + node.value;
  if(!node.left && !node.right){
    ans.push(newSum);
    return;
  }
  
  add(node.left, ans, newSum);
  add(node.right, ans, newSum);
}

:::

<br>

:::spoiler 月

A even-better solution with extra param in function

function branchSums(root, sum = 0, sums = []) {
  sum += root.value;
  if(!root.left && !root.right){
    sums.push(sum);
  }
  if(root.left){
    branchSums(root.left, sum, sums);
  }
  if(root.right){
    branchSums(root.right, sum, sums);
  }
  return sums
}

:::

<br>

---

## Supplement: category of DFS

### DFS Pre-order

<img src="https://res.cloudinary.com/practicaldev/image/fetch/s--jhfHLfge--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_66%2Cw_880/https://dev-to-uploads.s3.amazonaws.com/i/qpsgkhgccjrjn9ybxb6l.gif">

def pre_order(node):
    if node == None:
        return
    print(node.val)
    pre_order(node.left)
    pre_order(node.right)

---

### DFS In-order

<img src="https://res.cloudinary.com/practicaldev/image/fetch/s--zaYuwulZ--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_66%2Cw_880/https://dev-to-uploads.s3.amazonaws.com/i/w0z2pz1f7th1k0ut8rbr.gif">

def in_order(node):
    if node == None:
        return
    in_order(node.left)
    print(node.val)
    in_order(node.right)

---

### DFS Post-order

<img src="https://res.cloudinary.com/practicaldev/image/fetch/s--UFh1HPf7--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_66%2Cw_880/https://dev-to-uploads.s3.amazonaws.com/i/zv1x6vo9p8cqopqzod0n.gif">

def post_order(node):
    if node == None:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.val)