adepeju.
All posts
DSARecursionBinary Trees

Binary Search Trees — Branch Sums

A walkthrough of the Branch Sums problem — summing every root-to-leaf path in a binary tree using recursion and closures.

Adepeju Peace Orefejo Adepeju Peace Orefejo
·

What is a Binary Tree?

A binary tree is a data structure where each node has its own value, but also points to a left and a right child node. Each node is typically modelled as a class (or object) with three properties: value, left, and right. The left and right properties then point to their own nodes, forming a recursive structure.

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Problem: Branch Sums

We want to write a function that takes the root of a binary tree and returns the sum of every branch — that is, the sum of all node values from the root down to each leaf.

For a given branch, the sum is:

node.value + node.left.value + node.left.left.value + ...

Example Tree

               1
           /       \
       2               3
     /   \           /   \
   4       5       6       7
  / \     / \     / \     / \
 8   9  10  11  12  13  14  15

Expected Output (all branch sums)

  • 1 + 2 + 4 + 8 = 15
  • 1 + 2 + 4 + 9 = 16
  • 1 + 2 + 5 + 10 = 18
  • 1 + 2 + 5 + 11 = 19
  • 1 + 3 + 6 + 12 = 22
  • 1 + 3 + 6 + 13 = 23
  • 1 + 3 + 7 + 14 = 25
  • 1 + 3 + 7 + 15 = 26

Solution

function branchSums(root) {
  const total = [];
  const sum = 0;

  // Inner function — total & sum are accessible via closure
  function sumRecursively(node, sum) {
    // Base case: if the current node is null, stop recursing
    if (!node) return;

    // If we have a valid node, add its value to the running sum
    const newSum = sum + node.value;

    // If we're at a leaf (no children), we've completed a branch — record it
    if (!node.left && !node.right) {
      total.push(newSum);
      return;
    }

    // Otherwise, recurse down the left and right subtrees
    sumRecursively(node.left, newSum);
    sumRecursively(node.right, newSum);
  }

  // Kick off the recursion from the root with a starting sum of 0
  sumRecursively(root, sum);

  return total;
}

How It Works — Step by Step

Let's trace through the branch 1 → 2 → 4 → 8 to see how the recursion unfolds.

Iteration 1 — Root node (value: 1)

sumRecursively(root, 0) is called.

  • Base case check: Does the node exist? ✅ Yes, good to go.
  • Logic: newSum = 0 + 1 = 1
  • Node has children, so we recurse on both left (2) and right (3).

Iteration 2 — Left child (value: 2)

sumRecursively(node(2), 1) is called.

  • Base case check: Node exists ✅
  • Logic: newSum = 1 + 2 = 3
  • Node has children, so we recurse on both left (4) and right (5).

Iteration 3 — Left child (value: 4)

sumRecursively(node(4), 3) is called.

  • Base case check: Node exists ✅
  • Logic: newSum = 3 + 4 = 7
  • Node has children, so we recurse on both left (8) and right (9).

Iteration 4 — Left child (value: 8)

sumRecursively(node(8), 7) is called.

  • Base case check: Node exists ✅
  • Logic: newSum = 7 + 8 = 15
  • Leaf node check: No left or right child ✅ → total.push(15) and return.

The function then backtracks and follows the same process for every other branch, eventually returning:

[15, 16, 18, 19, 22, 23, 25, 26]

Key Concepts Used

  • Recursion — the function calls itself on each child node, naturally traversing the tree depth-first.
  • Closure — the inner sumRecursively function has access to the total array from its outer scope, so we don't need to pass it as a parameter.
  • Base cases — two are needed: one to handle null nodes, and one to detect leaf nodes and record the completed branch sum.

© 2026 adepeju orefejo