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.

Example:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

Input: root = [1,2,3], targetSum = 5
Output: false

Input: root = [1,2], targetSum = 0
Output: false

Clarifying Questions

  1. Q: Can the target sum be negative or zero? A: Yes, the target sum can be negative or zero.

  2. Q: What should we return if the tree is empty? A: If the tree is empty, we should return false because there cannot be any valid path.

  3. Q: Is it possible to have negative values in the tree nodes? A: Yes, the tree can contain negative values.

Strategy

We’ll use a Depth-First Search (DFS) approach to solve this problem. We start from the root and traverse down to the leaf nodes. As we traverse each path, we keep a cumulative sum to keep track of the current path sum. Once we reach a leaf node, we check if the cumulative sum equals the target sum. If any path equals the target sum, we return true. If we traverse all paths and find none that equals the target sum, we return false.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // If root is null, return false
        if (root == null) {
            return false;
        }
        
        // If we are at a leaf node, check if the current path sum equals the target sum
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        
        // Subtract the value of current node from targetSum before going deeper to children
        int remainingSum = targetSum - root.val;
        
        // Recursively check for left and right subtrees
        return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum);
    }
}

Time Complexity

The time complexity for this solution is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once. In the worst case, we have to traverse all the way to the leaf nodes, which requires visiting all nodes.

The space complexity is O(H), where H is the height of the tree. This is the space required for the call stack during the recursive calls. In the worst case (in a skewed binary tree), the height H can be equal to N, resulting in a space complexity of O(N). In a balanced tree, the height would be log(N), resulting in a space complexity of O(log N).

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