Given a binary tree and a target sum, find all root-to-leaf paths where each path’s sum equals the given target sum. A leaf is a node with no children.
Sample Input:
Tree:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Target Sum: 22
Expected Output:
[
[5, 4, 11, 2],
[5, 8, 4, 5]
]
In this example, there are two root-to-leaf paths with the sum of 22: 5 -> 4 -> 11 -> 2 and 5 -> 8 -> 4 -> 5.
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, 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.
Now, let’s provide the C++ solution with comments explaining the code:
#include <iostream>
#include <vector>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void findPaths(TreeNode* root, int sum, std::vector<int>& currentPath, std::vector<std::vector<int>>& result) {
// Base case: if the root is null, we can't proceed further
if (root == nullptr) {
return;
}
// Add the current node to the current path
currentPath.push_back(root->val);
// If it's a leaf node and its value equals the remaining sum, we have a valid path
if (root->left == nullptr && root->right == nullptr && root->val == sum) {
result.push_back(currentPath);
}
// Recursively check the left and right subtrees
findPaths(root->left, sum - root->val, currentPath, result);
findPaths(root->right, sum - root->val, currentPath, result);
// Remove the current node from the current path to backtrack
currentPath.pop_back();
}
std::vector<std::vector<int>> pathSum(TreeNode* root, int sum) {
std::vector<std::vector<int>> result;
std::vector<int> currentPath;
findPaths(root, sum, currentPath, result);
return result;
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(8);
root->left->left = new TreeNode(11);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(4);
root->left->left->left = new TreeNode(7);
root->left->left->right = new TreeNode(2);
root->right->right->left = new TreeNode(5);
root->right->right->right = new TreeNode(1);
int targetSum = 22;
// Find all root-to-leaf paths with the target sum
std::vector<std::vector<int>> paths = pathSum(root, targetSum);
// Print the result
std::cout << "Root-to-leaf paths with the sum " << targetSum << " are:\n";
for (const auto& path : paths) {
for (int num : path) {
std::cout << num << " ";
}
std::cout << std::endl;
}
// Don't forget to free the allocated memory
// ...
return 0;
}
The pathSum function finds all root-to-leaf paths with the given target sum. It uses a helper function findPaths to perform a depth-first search (DFS) and track the current path. Whenever a valid path is found (i.e., a leaf node with the correct sum), it adds that path to the result vector.
In the given example, the function will correctly find the two root-to-leaf paths with the sum of 22, and the output will be:
Root-to-leaf paths with the sum 22 are:
5 4 11 2
5 8 4 5
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.