Print All Paths in a Binary Tree with a Given Sum - Visualization

Binary Trees

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given a binary tree and a target sum, print all root-to-leaf paths where the sum of all node values in the path equals the target sum. Each valid path must begin at the root and end at a leaf node. If there are no such paths, indicate so.

Examples❯

Input Tree Target Sum Paths Matching Sum Description
[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1, 5]
22 [[5, 4, 11, 2], [5, 8, 4, 5]] Two valid root-to-leaf paths sum to 22.
[1, 2, 3]
3 [[1, 2]] Only the left path [1 → 2] adds to 3.
[1, 2]
0 [] No root-to-leaf path adds to 0.
[7, 3, 4, 2, null, null, 1]
12 [[7, 3, 2], [7, 4, 1]] Two root-to-leaf paths match the target sum.
[] 5 [] Empty tree has no paths.
[5]
5 [[5]] Single-node tree where root equals target sum.

Solution❯

Understanding the Problem

We are given a binary tree and a target sum. Our task is to find and print all root-to-leaf paths such that the sum of the node values along each path equals the target sum.

To solve this, we need to understand that a path must start from the root and end at a leaf node (a node with no children). We should explore all such paths in the tree and check their cumulative sum.

Step-by-Step Solution with Example

Step 1: Choose a traversal strategy

We'll use Depth-First Search (DFS) because we want to explore all paths from the root to each leaf node. At every node, we'll keep track of the current path and the sum so far.

Step 2: Use recursion with backtracking

As we go deeper into the tree, we append the current node's value to our path and subtract it from the remaining sum. If we reach a leaf and the remaining sum is zero, we add that path to our result. Then we backtrack to explore other paths.

Step 3: Let’s walk through an example

Consider the following binary tree and a target sum of 22:


       5
      /      4   8
    /   /    11  13  4
  /         7    2      1

We'll trace all paths from the root (5) to each leaf:

  • Path 1: 5 → 4 → 11 → 7 (Sum = 27)
  • Path 2: 5 → 4 → 11 → 2 (Sum = 22 ✅)
  • Path 3: 5 → 8 → 13 (Not a leaf)
  • Path 4: 5 → 8 → 4 → 1 (Sum = 18)

Only Path 2 matches our target sum. So the result is [[5, 4, 11, 2]].

Step 4: Implement the logic in code


def pathSum(root, targetSum):
    result = []

    def dfs(node, path, remaining):
        if not node:
            return
        path.append(node.val)
        remaining -= node.val

        if not node.left and not node.right and remaining == 0:
            result.append(list(path))
        else:
            dfs(node.left, path, remaining)
            dfs(node.right, path, remaining)

        path.pop()  # backtrack

    dfs(root, [], targetSum)
    return result

Edge Cases

Case 1: Tree with multiple valid paths

There may be more than one root-to-leaf path that meets the target sum. We must collect all such paths using DFS traversal.

Case 2: Only one valid path

Even if there’s only one valid path in the entire tree, our DFS will still correctly collect it.

Case 3: Single-node tree

If the tree contains only one node, we check if that single node's value equals the target. If yes, we return that path; otherwise, return an empty list.

Case 4: No valid path exists

Some trees will not have any path that sums up to the target. In such cases, our recursive DFS exhausts all possibilities and returns an empty list.

Case 5: Empty tree

If the tree is empty (i.e., root is None), there are no paths to explore, so the result should be an empty list.

Finally

This problem is a classic example of DFS with backtracking. It not only strengthens your understanding of recursion, but also demonstrates how to track state (path and remaining sum) and handle edge cases effectively.

Always remember to test your solution on edge cases like an empty tree, single-node trees, and trees with multiple valid paths to ensure correctness.

Algorithm Steps❯

  1. Given a binary tree and a target sum, initialize an empty path list and set the current sum to 0.
  2. Perform a depth-first search (DFS) traversal of the tree.
  3. At each node, add the node's value to the current path and update the current sum.
  4. If a leaf node is reached and the current sum equals the target sum, record or print the current path.
  5. Recursively explore the left and right subtrees.
  6. Backtrack by removing the current node from the path before returning to the previous level.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void printPath(int path[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", path[i]);
    }
    printf("\n");
}

void dfs(TreeNode* root, int targetSum, int currentSum, int path[], int level) {
    if (!root) return;
    path[level] = root->val;
    currentSum += root->val;
    if (!root->left && !root->right && currentSum == targetSum) {
        printPath(path, level + 1);
    }
    dfs(root->left, targetSum, currentSum, path, level + 1);
    dfs(root->right, targetSum, currentSum, path, level + 1);
}

void printPaths(TreeNode* root, int targetSum) {
    int path[100];
    dfs(root, targetSum, 0, path, 0);
}

int main() {
    TreeNode* root = createNode(5);
    root->left = createNode(4);
    root->right = createNode(8);
    root->left->left = createNode(11);
    root->left->left->left = createNode(7);
    root->left->left->right = createNode(2);
    root->right->left = createNode(13);
    root->right->right = createNode(4);
    root->right->right->right = createNode(1);
    printPaths(root, 22);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...