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

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

Sample Output

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

Hints

Hint 1

Try traversing the Binary Tree in a depth-first-search-like fashion.

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.

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.

Optimal Space & Time Complexity

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

Copy
1// This is the class of the input root.
2// Do not edit it.
3class BinaryTree {
4  constructor(value) {
5    this.value = value;
6    this.left = null;
7    this.right = null;
8  }
9}
10
11function branchSums(root) {
12    const sums = []
13  findSumOfNode(root, 0, sums)
14    return sums
15}
16
17function findSumOfNode(node, runningSum, sums) {
18    // create a array of nodes
19    if (!node) return;
20    
21    const newRunningSum = runningSum + node.value;
22    if(!node.left && !node.right) {
23        sums.push(newRunningSum);
24        return;
25    }
26    
27    findSumOfNode(node.left, newRunningSum, sums);
28    findSumOfNode(node.right, newRunningSum, sums);
29    
30}

🧤