Given a binary tree and a target sum, find the total number of all paths in the tree such that the sum of the values along the path equals the given target sum. The paths can start and end at any node in the tree, but they must go in the downward direction.
Table of Contents
Sample Input:
Tree:
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Target Sum: 8
Expected Output:
3
In this example, there are three paths in the tree whose sum is equal to 8:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
Time and Space Complexity:
The time complexity of the algorithm is O(n^2), where ‘n’ is the number of nodes in the binary tree. In the worst case, we may need to explore all possible paths in the tree, and each path can have a maximum length of ‘n’. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the tree.
C++ solution:
#include <iostream>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int countPaths(TreeNode* root, int targetSum) {
if (root == nullptr) {
return 0;
}
// Check the number of paths that start at the current node and go downwards
int pathsFromRoot = countPathsFromNode(root, targetSum);
// Recursively check the left and right subtrees
int pathsFromLeft = countPaths(root->left, targetSum);
int pathsFromRight = countPaths(root->right, targetSum);
// Return the total number of paths in the tree
return pathsFromRoot + pathsFromLeft + pathsFromRight;
}
int countPathsFromNode(TreeNode* node, int targetSum) {
if (node == nullptr) {
return 0;
}
// Check if the current node itself contributes to the target sum
int paths = 0;
if (node->val == targetSum) {
paths++;
}
// Recursively check the left and right subtrees
paths += countPathsFromNode(node->left, targetSum - node->val);
paths += countPathsFromNode(node->right, targetSum - node->val);
return paths;
}
int pathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return 0;
}
// Count the total number of paths in the binary tree
return countPaths(root, targetSum);
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(10);
root->left = new TreeNode(5);
root->right = new TreeNode(-3);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(2);
root->right->right = new TreeNode(11);
root->left->left->left = new TreeNode(3);
root->left->left->right = new TreeNode(-2);
root->left->right->right = new TreeNode(1);
int targetSum = 8;
// Find the total number of paths with the target sum
int totalPaths = pathSum(root, targetSum);
std::cout << "The total number of paths with the sum " << targetSum << " is: " << totalPaths << std::endl;
// Don't forget to free the allocated memory
// ...
return 0;
}
The pathSum function calculates the total number of paths in the binary tree whose sum equals the target sum. It uses a helper function countPaths to perform a recursive depth-first search (DFS) to count the number of paths that start at each node and go downwards. Another helper function countPathsFromNode calculates the number of paths that start at a specific node and go downwards.
In the given example, the function will correctly find three paths whose sum is 8, and the output will be 3.
As mentioned earlier, the time complexity is O(n^2) due to exploring all possible paths in the worst case, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the binary tree.