Given a binary tree and a target sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given target sum. A leaf is a node with no children.
Table of Contents
Sample Input:
Tree:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Target Sum: 22
Expected Output:
true
In this example, there is a root-to-leaf path with the sum of 22: 5 -> 4 -> 11 -> 2.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to check if there is a path with the given sum. 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>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
bool hasPathSum(TreeNode* root, int sum) {
// Base case: if the root is null, the path sum is not possible
if (root == nullptr) {
return false;
}
// If it's a leaf node and its value equals the remaining sum, we have a path
if (root->left == nullptr && root->right == nullptr && root->val == sum) {
return true;
}
// Recursively check the left and right subtrees
bool hasPathLeft = hasPathSum(root->left, sum - root->val);
bool hasPathRight = hasPathSum(root->right, sum - root->val);
// Return true if either of the subtrees has a valid path sum
return hasPathLeft || hasPathRight;
}
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->right = new TreeNode(1);
int targetSum = 22;
// Check if the binary tree has a path with the target sum
if (hasPathSum(root, targetSum)) {
std::cout << "The binary tree has a path with the sum " << targetSum << ".\n";
} else {
std::cout << "The binary tree does not have a path with the sum " << targetSum << ".\n";
}
// Don't forget to free the allocated memory
// ...
return 0;
}
The hasPathSum function recursively checks if a path with the given sum exists in the binary tree. It starts from the root node and traverses down the tree, subtracting the current node’s value from the target sum as it goes. When it reaches a leaf node, it checks if the remaining sum is zero (indicating a valid path).
In the given example, the function will correctly find the path with the sum of 22, and the output will be true.
As mentioned earlier, the time complexity is O(n) as we need to visit each node once, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the binary tree.