algoadvance

Leetcode 112. Path Sum

Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.

Clarifying Questions

1. Q: Can targetSum be negative? A: Yes, targetSum can be any integer, including negative values.

2. Q: What should be returned if the tree is empty? A: Return false.

3. Q: Are the node values in the tree restricted to any particular range? A: For this problem, assume the node values can be any integer.

4. Q: Is the function supposed to consider paths that do not start at the root or end at the leaves? A: No, only root-to-leaf paths should be considered.

Strategy

1. This problem can be solved using Depth-First Search (DFS).
2. At each node, we will subtract the node’s value from targetSum and check if we have reached a leaf node where the remaining targetSum equals zero.
3. If such a path is found, we return true.
4. If we reach a leaf node and the targetSum does not equal zero, we continue the search.
5. Recursion is an effective way to implement DFS in this context.

Code

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;

        // Check if we are at a leaf node and if current value is equal to targetSum
        if (!root->left && !root->right) return targetSum == root->val;

        // Recurse for left and right subtrees, reducing targetSum by root's value
        int newTargetSum = targetSum - root->val;
        return hasPathSum(root->left, newTargetSum) || hasPathSum(root->right, newTargetSum);
    }
};

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree.
  • In the worst case, we visit each node once.
• Space Complexity: O(H), where H is the height of the tree.
  • This accounts for the recursion stack. In the worst case (unbalanced tree), H could be as bad as N; in the best case (balanced tree), H would be log(N).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?