Branch Sums

A corgi smiling happily

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

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

Sample Output

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

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}

🧤

Do you have any questions, or simply wish to contact me privately? Don’t hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

Subscribe to my newsletter

Get email from me about my ideas, full-stack development resources, tricks and tips as well as exclusive previews of upcoming articles.

No spam. Just the highest quality ideas you’ll find on the web.