Branch Sums

Tags

Branch Sums

Category

Binary Trees

Difficulty

Easy

Problem Statement

Given a binary tree, return a list of its branch sums ordered from leftmost branch to rightmost branch. A branch sum is the sum of all node values along a path from the root to a leaf node.

Intuition

Every root-to-leaf path defines a branch. As we traverse from root to leaf, we accumulate the running sum. When we reach a leaf (a node with no children), the running sum is a branch sum. A pre-order DFS naturally visits left branches before right branches, giving us the correct left-to-right ordering.

Approach

  1. Initialize an empty list to store branch sums.
  2. Perform a recursive DFS starting at the root with a running sum of 0.
  3. At each node, add the node's value to the running sum.
  4. If the node is a leaf (no left or right child), append the running sum to the results list.
  5. Otherwise, recurse on the left child (if it exists) and then the right child (if it exists), passing along the updated running sum.
  6. Return the results list.

Pseudocode

function branchSums(root):
    sums = []
    dfs(root, 0, sums)
    return sums

function dfs(node, runningSum, sums):
    if node is null:
        return
    runningSum += node.value
    if node.left is null and node.right is null:
        sums.append(runningSum)
        return
    dfs(node.left, runningSum, sums)
    dfs(node.right, runningSum, sums)

Time & Space Complexity

  • Time: O(n) where n is the number of nodes in the tree. Every node is visited exactly once.
  • Space: O(n) — the results list can contain up to n/2 sums (number of leaves in a balanced tree), and the recursion stack can be O(n) in the worst case (skewed tree) or O(log n) for a balanced tree.

Key Insights

  • A leaf node is defined as a node with no left and no right child.
  • The left-to-right ordering of branch sums is guaranteed by visiting the left subtree before the right subtree.
  • The running sum is passed by value (or as a parameter), so each recursive path maintains its own independent sum.

Edge Cases

  • A tree with a single node (the root is also a leaf): return a list with just the root's value.
  • A completely left-skewed or right-skewed tree: only one branch sum exists.
  • Nodes with negative values — the running sum can decrease.
  • The root is null: return an empty list.

Linked mentions