Path Sum

Problem Statement

LeetCode-112: 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.

Approach

We can use a recursive DFS algorithm to traverse the tree with a base case of null node:

1. The current node is null - return false.
2. The current node is a leaf node and the sum of the path from root to this leaf node is equal to targetSum - return true.
3. Recursively check the left and right subtree with the updated targetSum as targetSum - root.val.

Implementation

Here is a java implementation of the DFS approach:

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }

    // leaf node and sum of path from root to 
    // this leaf node is equal to targetSum
    if (root.left == null && 
            root.right == null && 
            targetSum == root.val) {
        return true;
    }

    // recursively check left and right subtree
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

Complexity Analysis

The time complexity for the above approach is $O(N)$ where $N$ is the number of nodes in the binary tree. The space complexity is $O(H)$ where $H$ is the height of the binary tree which is the space used by the recursion stack.