Print All Paths in a Binary Tree with a Given Sum - Code Examples

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❯

Case 1: Normal Case (Tree with multiple valid paths)

In a typical binary tree with multiple levels, we may find more than one path that leads to a sum equal to the target. For example, in a tree where the root is 5, there could be different branches that sum up to 22, such as one going through 4 → 11 → 2 and another going through 8 → 4 → 5. We perform a depth-first traversal and whenever we reach a leaf, we check the accumulated path sum. If it matches the target, we add that path to our results.

Case 2: Single valid path

There might only be one valid path that matches the target sum. Suppose the tree is very small and has a path like 1 → 2 → 5 and the target is 8. In this case, only one path qualifies. DFS still works here, and it will find that single path.

Case 3: Single-node tree

For a tree that contains only one node, we check if the node’s value is equal to the target sum. If it matches, we return that one-element path. If not, we return an empty list because no path exists from root to a leaf (since it doesn't qualify as a leaf with the correct sum).

Case 4: No valid path

Sometimes, all paths may fail to add up to the required sum. This could be because the sum is too large or too small compared to what the node values allow. In such a case, we exhaust all paths using DFS and find nothing, so we return an empty list.

Case 5: Empty Tree

If the tree is empty (i.e., there is no root node), then there are no paths at all. Hence, the output should be an empty list regardless of the target sum.

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

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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__':
    # Construct binary tree example:
    #         5
    #        / \
    #       4   8
    #      /   / \
    #    11   13  4
    #    /  \       \
    #   7    2       1
    root = TreeNode(5,
            TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
            TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1))))
    printPaths(root, 22)