112. Path Sum

Problem Description

The problem presents a binary tree where each node contains an integer value. The goal is to find out if there is a path from the root node down to any leaf node such that the sum of the values of all the nodes along the path is equal to the given integer targetSum. A leaf node is defined as a node that does not have any children. If such a path exists, the function should return true; otherwise, it should return false.

Intuition

The solution to this problem is based on the Depth-First Search (DFS) algorithm. DFS is a common tree traversal method that can be used efficiently to search all possible paths in a tree from the root node down to the leaves.

The intuition behind using DFS in this particular problem is the need to explore each possible path fully before moving to an alternative path. We traverse down one branch of the tree, adding the values of each node we pass through, until we reach a leaf. Once at a leaf, we check if the accumulated sum is equal to targetSum.

If we hit a leaf and the sum does not equal targetSum, we backtrack and try a different path. This backtracking is naturally handled by the call stack in a recursive DFS approach.

Thus, the solution approach is to start from the root and explore each branch recursively, carrying forwards the cumulative sum. If at any point we reach a leaf and the sum matches targetSum, we return true. Otherwise, if we exhaust all paths and none meet the criteria, we return false.

As part of the recursion, we ensure two things:

1. If the current node is None (i.e., we've reached beyond a leaf), this path is not valid, and we return false.
2. When we reach a leaf node (both its children are None), we check if the cumulative sum equals targetSum and return the result of this comparison.

The provided code defines a nested dfs function inside the main function hasPathSum that handles the recursive traversal and the accumulation of the sum.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution utilizes a straightforward recursive DFS strategy. By defining a helper function dfs(root, s), we can keep track of the current sum s as we traverse down the tree. The base case checks if the current node root is None, meaning that the path has reached beyond a leaf node, and hence, it returns False since there cannot be a valid path through a non-existing node.

When the recursive function dfs is called, it performs the following steps:

1. It first checks if the current node is None. If true, the recursion stops and returns False.
2. If the current node is not None, it adds the node's value to the ongoing sum s.
3. Next, it checks if the current node is a leaf (both root.left and root.right are None). If it is a leaf, and s equals targetSum, it indicates that a valid path has been found and returns True.
4. If the current node is not a leaf, the function proceeds to call itself recursively for both the left and right children of the current node, if they exist (dfs(root.left, s) and dfs(root.right, s)).
5. The result of these recursive calls is combined using logical OR (or), which means if either the left or the right subtree has a valid path, the function will return True.

The dfs function encapsulates the logic for searching the tree and determining if a valid path exists that sums up to targetSum. It is initiated by passing the root of the tree and an initial sum of 0 to the dfs function.

Here is how the dfs function is implemented within the context of the provided solution code snippet:

1def dfs(root, s):
2    if root is None:  # Base case: empty node, return False
3        return False
4    s += root.val  # Increment the sum by the current node's value
5    # If it's a leaf and the sum matches targetSum, return True
6    if root.left is None and root.right is None and s == targetSum:
7        return True
8    # Recursively search the left and right subtrees
9    return dfs(root.left, s) or dfs(root.right, s)

And the hasPathSum function then calls this dfs function with the initial parameters:

1return dfs(root, 0)

In summary, the recursive function explores all possible paths from the root to each leaf, checking for a match against targetSum. It returns True as soon as a valid path is found, or False if no such path exists, effectively implementing a depth-first search for the problem at hand.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Assume we have the following binary tree and targetSum of 22.

1        5
2       / \
3      4   8
4     /   / \
5    11  13  4
6   /  \      \
7  7    2      1

Now, let's follow the dfs function to see how it works:

1. Begin at the root (node with value 5), with a starting sum s of 0. Call dfs(root=5, s=0).

2. At root (5), s becomes 5 (0 + 5). This node is not a leaf, so we make recursive calls for left and right children.

   • Call dfs(root=4, s=5) to continue on the left child.

3. At node 4, s becomes 9 (5 + 4). This is also not a leaf. Recursive call on left child.

   • Call dfs(root=11, s=9).

4. At node 11, s becomes 20 (9 + 11). Not a leaf, we have two children, so we make two recursive calls.

   • First, call dfs(root=7, s=20).
   • Then we will call dfs(root=2, s=20), but let's follow the first call for now.

5. At node 7, s becomes 27 (20 + 7). This is a leaf, but s is not equal to the targetSum of 22. Returns False.

   • Backtrack to node 11 and proceed with the second call, dfs(root=2, s=20).

6. At node 2, s becomes 22 (20 + 2). This is a leaf and s matches targetSum. Returns True.

Once True is encountered, the function does not need to explore any further branches. The propagation of True through the recursive calls will eventually lead to the hasPathSum function returning True, indicating that there is a path that adds up to the targetSum of 22.

The binary tree has successfully been searched with a depth-first approach to find a path sum that matches the target. In this case, the path with values [5, 4, 11, 2] yields the desired sum, and so our problem is solved with the function returning True.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the binary tree. The reason for this is that the code implements a depth-first search (DFS) algorithm, which visits each node exactly once in the worst-case scenario.

Space Complexity

The space complexity of the code is O(h), where h is the height of the binary tree. This space is used by the execution stack for recursive calls. In the worst-case scenario where the tree is completely unbalanced, the space complexity will be O(n). But on a balanced tree, the height h can be considered as O(log n), making the average space complexity O(log n).

Learn more about how to find time and space complexity quickly using problem constraints.