Print All Paths in a Binary Tree with a Given Sum

Problem and examples

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.

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.

How it works

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.

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void dfs(TreeNode* root, int targetSum, int currentSum, vector<int>& path) {
    if (!root) return;
    path.push_back(root->val);
    currentSum += root->val;
    if (!root->left && !root->right && currentSum == targetSum) {
        for (int val : path) cout << val << " ";
        cout << endl;
    }
    dfs(root->left, targetSum, currentSum, path);
    dfs(root->right, targetSum, currentSum, path);
    path.pop_back();
}

void printPaths(TreeNode* root, int targetSum) {
    vector<int> path;
    dfs(root, targetSum, 0, path);
}

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

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def printPaths(root, targetSum):
    def dfs(node, currentPath, currentSum):
        if not node:
            return
        currentPath.append(node.val)
        currentSum += node.val
        if not node.left and not node.right and currentSum == targetSum:
            print(currentPath)
        dfs(node.left, currentPath, currentSum)
        dfs(node.right, currentPath, currentSum)
        currentPath.pop()

    dfs(root, [], 0)

if __name__ == '__main__':
    root = TreeNode(5,
            TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
            TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1))))
    printPaths(root, 22)

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class AllPathsWithSum {
    public void printPaths(TreeNode root, int targetSum) {
        List<Integer> path = new ArrayList<>();
        dfs(root, targetSum, 0, path);
    }

    private void dfs(TreeNode node, int targetSum, int currentSum, List<Integer> path) {
        if (node == null) return;
        path.add(node.val);
        currentSum += node.val;
        if (node.left == null && node.right == null && currentSum == targetSum) {
            System.out.println(path);
        }
        dfs(node.left, targetSum, currentSum, path);
        dfs(node.right, targetSum, currentSum, path);
        path.remove(path.size() - 1);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);
        new AllPathsWithSum().printPaths(root, 22);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function printPaths(root, targetSum) {
    function dfs(node, path, sum) {
        if (!node) return;
        path.push(node.val);
        sum += node.val;
        if (!node.left && !node.right && sum === targetSum) {
            console.log([...path]);
        }
        dfs(node.left, path, sum);
        dfs(node.right, path, sum);
        path.pop();
    }
    dfs(root, [], 0);
}

const root = new TreeNode(5,
    new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
    new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));
printPaths(root, 22);

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func printPaths(root *TreeNode, targetSum int) {
    var dfs func(node *TreeNode, path []int, sum int)
    dfs = func(node *TreeNode, path []int, sum int) {
        if node == nil {
            return
        }
        path = append(path, node.Val)
        sum += node.Val
        if node.Left == nil && node.Right == nil && sum == targetSum {
            fmt.Println(path)
        }
        dfs(node.Left, path, sum)
        dfs(node.Right, path, sum)
    }
    dfs(root, []int{}, 0)
}

func main() {
    root := &TreeNode{5,
        &TreeNode{4, &TreeNode{11, &TreeNode{7, nil, nil}, &TreeNode{2, nil, nil}}, nil},
        &TreeNode{8, &TreeNode{13, nil, nil}, &TreeNode{4, nil, &TreeNode{1, nil, nil}}},
    }
    printPaths(root, 22)
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

type Node = Option<Rc<RefCell<TreeNode>>>;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Node,
    right: Node,
}

fn print_paths(root: Node, target_sum: i32) {
    fn dfs(node: &Node, path: &mut Vec<i32>, sum: i32, target: i32) {
        if let Some(n) = node {
            let n = n.borrow();
            path.push(n.val);
            let new_sum = sum + n.val;
            if n.left.is_none() && n.right.is_none() && new_sum == target {
                println!("{:?}", path);
            }
            dfs(&n.left, path, new_sum, target);
            dfs(&n.right, path, new_sum, target);
            path.pop();
        }
    }
    dfs(&root, &mut vec![], 0, target_sum);
}

fn main() {
    let root = Some(Rc::new(RefCell::new(TreeNode {
        val: 5,
        left: Some(Rc::new(RefCell::new(TreeNode {
            val: 4,
            left: Some(Rc::new(RefCell::new(TreeNode {
                val: 11,
                left: Some(Rc::new(RefCell::new(TreeNode { val: 7, left: None, right: None })));
                right: Some(Rc::new(RefCell::new(TreeNode { val: 2, left: None, right: None })));
            }))),
            right: None,
        }))),
        right: Some(Rc::new(RefCell::new(TreeNode {
            val: 8,
            left: Some(Rc::new(RefCell::new(TreeNode { val: 13, left: None, right: None })));
            right: Some(Rc::new(RefCell::new(TreeNode {
                val: 4,
                left: None,
                right: Some(Rc::new(RefCell::new(TreeNode { val: 1, left: None, right: None })));
            }))),
        }))),
    })));
    print_paths(root, 22);
}

Kotlin implementation

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun printPaths(root: TreeNode?, targetSum: Int) {
    fun dfs(node: TreeNode?, path: MutableList<Int>, sum: Int) {
        if (node == null) return
        path.add(node.value)
        val newSum = sum + node.value
        if (node.left == null && node.right == null && newSum == targetSum) {
            println(path)
        }
        dfs(node.left, path, newSum)
        dfs(node.right, path, newSum)
        path.removeAt(path.size - 1)
    }
    dfs(root, mutableListOf(), 0)
}

fun main() {
    val root = TreeNode(5,
        TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
        TreeNode(8, TreeNode(13), TreeNode(4, null, TreeNode(1))))
    printPaths(root, 22)
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func printPaths(_ root: TreeNode?, _ targetSum: Int) {
    func dfs(_ node: TreeNode?, _ path: inout [Int], _ sum: Int) {
        guard let node = node else { return }
        path.append(node.val)
        let newSum = sum + node.val
        if node.left == nil && node.right == nil && newSum == targetSum {
            print(path)
        }
        dfs(node.left, &path, newSum)
        dfs(node.right, &path, newSum)
        path.removeLast()
    }
    var path = [Int]()
    dfs(root, &path, 0)
}

let root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left?.left = TreeNode(11)
root.left?.left?.left = TreeNode(7)
root.left?.left?.right = TreeNode(2)
root.right?.left = TreeNode(13)
root.right?.right = TreeNode(4)
root.right?.right?.right = TreeNode(1)

printPaths(root, 22)

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function printPaths(root: TreeNode | null, targetSum: number): void {
    function dfs(node: TreeNode | null, path: number[], sum: number): void {
        if (!node) return;
        path.push(node.val);
        sum += node.val;
        if (!node.left && !node.right && sum === targetSum) {
            console.log([...path]);
        }
        dfs(node.left, path, sum);
        dfs(node.right, path, sum);
        path.pop();
    }
    dfs(root, [], 0);
}

const root = new TreeNode(5,
    new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
    new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));

printPaths(root, 22);