How to Count the Path Sum from a Binary Tree using Depth First Search Algorithm?

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

Compute the Path Sum in Binary Tree using DFS Algorithm

The binary tree problems are most likely to be solved using recursion, which we will implement a Depth First Search algorithm to go through all the nodes.

As the path sum does not begin from the root, hence, the total path sum would be the following equation:

1

F(root, sum) = F(root>left, sum) + F(root>right, sum) + G(root, sum)

F(root, sum) = F(root>left, sum) + F(root>right, sum) + G(root, sum)

Where G is a function to compute the path sum from the exactly the root.

We can deduct the current node value from the sum and pass it down to the tree, until the remainder of the sum is exactly the current node’s value, when we increment the answer by one.

The following is the C++ implementation that counts the path sum given a root using the Depth First Search Algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
       if (root == nullptr) return 0;
       return pathFromRoot(root, sum) + 
              pathSum(root->left, sum) +
              pathSum(root->right, sum);
    }
    
    int pathFromRoot(TreeNode* root, int sum) {
        if (root == nullptr) return 0;
        int r1 = pathFromRoot(root->left, sum - root->val);
        int r2 = pathFromRoot(root->right, sum - root->val); 
        int ans = (root->val == sum) ? 1 : 0;
        return ans + r1 + r2;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
       if (root == nullptr) return 0;
       return pathFromRoot(root, sum) + 
              pathSum(root->left, sum) +
              pathSum(root->right, sum);
    }
    
    int pathFromRoot(TreeNode* root, int sum) {
        if (root == nullptr) return 0;
        int r1 = pathFromRoot(root->left, sum - root->val);
        int r2 = pathFromRoot(root->right, sum - root->val); 
        int ans = (root->val == sum) ? 1 : 0;
        return ans + r1 + r2;
    }
};

The space complexity is O(N) and the time complexity is O(N^2) and the best case is O(NlogN).

–EOF (The Ultimate Computing & Technology Blog) —