Branch Sum in Binary Tree — Competitive Programming with Time and Space Complexity

Question

Write a function that takes in a Binary Tree and returns a list of its branch sums ordered from leftmost branch sum to rightmost branch sum.

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 is given as:

Sample Input Tree

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

Solution

public class BinaryTree
{
public BinaryTree(int value)
{
this.value = value;
this.left = null;
this.right = null;
}
public int value;
public BinaryTree left;
public BinaryTree right;
}
private void GetBranchSum(BinaryTree tree, int runningSum, List<int> branchSum)
{
if (tree == null) return;
int totalSum = runningSum + tree.value;
}
List<int> branchSum = new List<int>();
GetBranchSum(tree, 0, branchSum)
private static void GetBranchSum(BinaryTree tree, int runningSum, List<int> branchSum)
{
if (tree == null) return;

int totalSum = runningSum + tree.value;
if (tree.left == null && tree.right == null)
{
branchSum.Add(totalSum);
return;
}

}
Calculate the first branch’s sum
private static void GetBranchSum(BinaryTree tree, int runningSum, List<int> branchSum)
{
if (tree == null) return;

int totalSum = runningSum + tree.value;
if (tree.left == null && tree.right == null)
{
branchSum.Add(totalSum);
return;
}
GetBranchSum(tree.left, totalSum, branchSum);
GetBranchSum(tree.right, totalSum, branchSum);
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store