Print All Paths With a Given Sum in a Binary Tree

1. Introduction

A binary tree is a hierarchical data structure in which each node has at most two children. Each node of a binary tree has 3 elements: a data element to hold an integer value and two children pointers to point its left and right children. In this tutorial, we’ll solve a binary tree path sum problem with the pre-order tree traversal algorithm.

2. Binary Tree Path Sum Problem

Given the node of a binary tree and an integer , we want to print all paths where the sum of the values along each path equals . The path does not need to start at the node or end with a leaf node. However, it must go downwards. That is, we traverse the path from parent nodes to child nodes.

Also, the path can be a single node whose data value is . For example, we have 4 paths that satisfy the of in the following binary tree:

In the extreme case, we can have a binary tree whose node values are all and our is also . In this case, we need to print out all possible paths that go downwards.

3. Pre-Order Path Sum Sequence

For each tree node, we can record the path sum value from the node to this node:

we can use the pre-order tree traversal to calculate the path sum for each tree node. In a pre-order traversal, we first visit the node. Then, we visit the left and right subtrees. Therefore, we can guarantee a downward path between any two nodes in a pre-order traversal sequence. For example, the pre-order path sum sequence of the example binary tree is:

Each element of the pre-order traversal sequence contains two values: the current tree node and the path sum from the node to the current tree node:

structure PathSumNode:
    // A structure to hold a tree node and the path sum from the root node to this node.
    node: TreeNode
    sum: int

We can use a recursive pre-order tree traversal algorithm to construct the path sum sequence:

algorithm PreOrderPathSum(root):
    // INPUT
    //    root = The root node of the input binary tree
    // OUTPUT
    //    The sequence that represents the path sum values from the root to every node
    sequence <- an empty list
    PathSumRec(root, 0, sequence)
    
    return sequence

algorithm PathSumRec(node, sum, sequence):
    // INPUT
    //    node = The current node in the binary tree
    //    sum = The sum of values from the root to the parent of the current node
    //    sequence = The sequence list to which the current node's path sum will be appended
    // OUTPUT
    //    Updates the sequence list with the current node's path sum information
    if node is not null:
        sum <- sum + node.data
        Append (node, sum) to the back of sequence
        
        PathSumRec(node.left, sum, sequence)
        PathSumRec(node.right, sum, sequence)

In this algorithm, we start with the node. We first put its path sum node into the sequence. Then, we recursively visit its left and right children. In each recursive call, we add the current tree node’s data into the accumulated path sum value. Therefore, the field contains the path sum value from the node to the current tree node.

If the binary tree contains nodes, the overall running time of this algorithm is  since we visit each node only once.

4. Print All Paths with Target Sum

We can calculate the path sum between any two tree nodes in constant time with the pre-order path sum sequence. For any two nodes in the path sum sequence with indexes and (), the path sum between the two nodes is . For example, we can calculate the path sum between node 5 and node 3 in the example tree as .

Based on this formula, we can find all paths whose path sum values are equal to :

algorithm PrintAllPathsWithTargetSum(sequence, targetSum):
    // INPUT
    //    sequence = The pre-order path sum sequence (0-based indexing)
    //    targetSum = The target sum to find in the binary tree paths
    // OUTPUT
    //    Print all paths for which the sum equals targetSum
    for i <- 0 to length(sequence) - 1:
        for j <- i to length(sequence) - 1:
            pathSum <- sequence[j].sum - sequence[i].sum + sequence[i].node.data
            if pathSum = targetSum:
                PrintPath(sequence[i].node, sequence[j].node)

In this algorithm, we search all pairs of tree nodes as the path start and end nodes. For each pair of nodes, we calculate its path sum and compare the result with . If they are the same, we then print the path between these two nodes.

We can use a top-down approach to print the path between any two tree nodes:

algorithm PrintPath(source, target):
    // INPUT
    //    source = The source node of the path
    //    target = The target node of the path
    // OUTPUT
    //    Print the data values along the path from source to target
    path <- an empty list
    if FindPath(source, target, path):
        output path

algorithm FindPath(node, target, path):
    // INPUT
    //    node = The current node from which the search starts or continues
    //    target = The target node we want to reach in the path
    //    path = The list of data values representing the path from source to node
    // OUTPUT
    //    Returns true if the target node is found in the path from the source node, false otherwise. 
    //    Also, updates the path list with the correct path if the target node is found.
    if node is null:
        return false
    
    Add node.data to the back of path
    if node = target:
        return true
    
    if FindPath(node.left, target, path) or FindPath(node.right, target, path):
        return true
    
    Remove node.data from the back of path
    
    return false

This algorithm also uses the pre-order traversal to search the binary tree. In each recursive call, we first append the current node into the path. We stop the searching when we locate the node. Otherwise, we continue the search on the current node’s left and right subtree.

To find all paths, we use a nested loop to search all possible pairs of binary tree nodes. This takes time. Also, when we find a path whose path sum is , we need an extra time to print the path. Therefore, the overall time complexity of the algorithm is .

5. Conclusion

In this tutorial, we showed how to construct a binary tree path sum sequence in linear time. Based on this sequence, we can print all paths with in time.