Print All Paths in a Binary Tree with a Given Sum

Algorithm Steps

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.

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

Python

Java

JavaScript

C++

Kotlin

Swift

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)