# Branch Sums in a Binary Tree

Given a Binary Tree, compute the sum of all the branches in the tree. 1 branch is the path from the root to a leaf.

## Branch Sums - Solution

We are going to use recursion to solve this problem. But it is important to understand what a branch is.

Consider the binary tree

``````            
/     \
       
``````
• Left branch sum = `-` = `3`
• Right branch sum = `-` = `4`
• Output `[3, 4]`

### Key points

• We need to keep track of a `sum` array variable, that will keep count on the total sum value that is being calulated.
• One important point is to check whether we have reached the leaf node or not. If we have reached the end, that is the point when we are going to push our `runningSum` to the global `sums` array.

### Algorithm

1. Declare a variable `sums` and initialize it to an empty array.
2. We create a `branchSumsHelper(tree, runningSum, sums)` helper method that we will use to recurse.
3. The base case will be when there are NO `left subtree` and no `right subtree`. This means that the node we are currently at is a `leaf node`.
4. If the node is a `leaf node`, push it to the `sums` array and return from the recursion.
5. Otherwise, recurse with `branchSumsHelper(tree.left, newRunningSum, sumsArray)` and `branchSumsHelper(tree.right, newRunningSum, sumsArray)`
6. The `runningSum` variable takes care of the current sum that we are adding, hence, we compute the running sum as ` newRunningSum = runningSum + tree.value;`

### Complexity analysis

• Time Complexity: `O(n)`
• Space Complexity: `O(n)` - Because the tree can be a skewed tree.
Solve Branch Sums in a Binary Tree on Algochurn

## Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn