ūüĎč
Welcome to my blog!

Branch Sums

Learn how to calculate the sums of all branches in a binary tree, a fundamental task in algorithmic interviews and data structure analysis.

Branch Sums
BT
easy

Published At

7/3/2021

Reading Time

~ 3 min read

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

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

Sample Output

js[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
js[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

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

Solution-1
js// This is the class of the input root.
// Do not edit it.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
 
function branchSums(root) {
	const sums = []
  findSumOfNode(root, 0, sums)
	return sums
}
 
function findSumOfNode(node, runningSum, sums) {
	// create a array of nodes
	if (!node) return;
	
	const newRunningSum = runningSum + node.value;
	if(!node.left && !node.right) {
		sums.push(newRunningSum);
		return;
	}
	
	findSumOfNode(node.left, newRunningSum, sums);
	findSumOfNode(node.right, newRunningSum, sums);
	
}
Solution-1
js// This is the class of the input root.
// Do not edit it.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
 
function branchSums(root) {
	const sums = []
  findSumOfNode(root, 0, sums)
	return sums
}
 
function findSumOfNode(node, runningSum, sums) {
	// create a array of nodes
	if (!node) return;
	
	const newRunningSum = runningSum + node.value;
	if(!node.left && !node.right) {
		sums.push(newRunningSum);
		return;
	}
	
	findSumOfNode(node.left, newRunningSum, sums);
	findSumOfNode(node.right, newRunningSum, sums);
	
}

ūüߧ

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 ūüôŹ

Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

  • In-depth looks at my covert projects and musings to ignite your imagination.
  • Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
  • A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.