Branch Sums in a Binary Tree

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

            [1]
          /     \
       [2]       [3]

• Left branch sum = [1]-[2] = 3
• Right branch sum = [1]-[3] = 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.