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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How many ways can you arrange the three letters A, B and C?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

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.

Not Sure What to Study? Take the 2-min Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Python Solution

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.current_sum = left
6        self.right = right
7
8class Solution:
9    def hasPathSum(self, root: Optional[TreeNode], target_sum: int) -> bool:
10        """
11        Determines if the tree has a root-to-leaf path such that
12        adding up all the values along the path equals the given sum.
13
14        :param root: TreeNode, the root of the binary tree
15        :param target_sum: int, the target sum to be achieved
16        :return: bool, True if such a path exists, False otherwise
17        """
18      
19        def dfs(node, current_sum):
20            """
21            Depth-first search helper function that traverses the tree
22            to find a root-to-leaf path that sums to the target_sum.
23
24            :param node: TreeNode, the current node being traversed
25            :param current_sum: int, the sum of the values from the root node up to the current node
26            :return: bool, True if a path is found, False otherwise
27            """
28            if node is None:
29                # Base case: if the current node is None, no path exists
30                return False
31          
32            # Update the current_sum by adding the current node's value
33            current_sum += node.val
34          
35            # Check if the current node is a leaf and matches the target_sum
36            if node.left is None and node.right is None and current_sum == target_sum:
37                return True
38          
39            # Recursively search in the left and right subtrees for the path
40            # If either subtree returns True, a valid path has been found
41            return dfs(node.left, current_sum) or dfs(node.right, current_sum)
42
43        # Start DFS traversal from the root with an initial sum of 0
44        return dfs(root, 0)
45

Java Solution

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8  
9    TreeNode() {}
10  
11    TreeNode(int val) {
12        this.val = val;
13    }
14  
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23    /**
24     * Returns true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given target sum.
25     *
26     * @param root The root of the binary tree.
27     * @param targetSum The target sum to find.
28     * @return True if such a path exists, otherwise false.
29     */
30    public boolean hasPathSum(TreeNode root, int targetSum) {
31        return hasPathSumDFS(root, targetSum);
32    }
33
34    /**
35     * Helper method to perform depth-first search to find the path sum.
36     *
37     * @param node The current node being visited.
38     * @param currentSum The sum accumulated so far.
39     * @return True if a path with the given sum is found, otherwise false.
40     */
41    private boolean hasPathSumDFS(TreeNode node, int currentSum) {
42        // If the node is null, we've hit a dead end and should return false.
43        if (node == null) {
44            return false;
45        }
46      
47        // Subtract the value of current node from current sum.
48        currentSum -= node.val;
49      
50        // Check if the current node is a leaf and the current sum equals zero,
51        // which means we've found a path with the required sum.
52        if (node.left == null && node.right == null && currentSum == 0) {
53            return true;
54        }
55      
56        // Recursively check the left and right subtrees for the remaining sum.
57        // If either subtree returns true, a path has been found.
58        return hasPathSumDFS(node.left, currentSum) || hasPathSumDFS(node.right, currentSum);
59    }
60}
61

C++ Solution

1// Definition for a binary tree node
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    // Constructor to initialize a tree node with a value and optional left and right children
7    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8    // Constructor to initialize a tree node with a value and both children
9    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14    // Checks if the binary tree has a root-to-leaf path that sums up to the targetSum
15    bool hasPathSum(TreeNode* root, int targetSum) {
16        // Lambda function that performs depth-first search on the tree to find path sum
17        // [&] captures local variables by reference
18        std::function<bool(TreeNode*, int)> dfs = [&](TreeNode* node, int sumSoFar) -> bool {
19            // If the node is null, return false as we've reached beyond a leaf node
20            if (!node) return false;
21          
22            // Add the current node's value to the running sum
23            sumSoFar += node->val;
24          
25            // Check if the current node is a leaf and the sum equals the targetSum
26            if (!node->left && !node->right && sumSoFar == targetSum) {
27                return true;
28            }
29          
30            // Continue searching in the left and right subtrees
31            // If any of the recursive calls return true, the whole expression will be true
32            // Utilize the short-circuit evaluation of the '||' operator
33            return dfs(node->left, sumSoFar) || dfs(node->right, sumSoFar);
34        };
35      
36        // Start the depth-first search from the root node with an initial sum of 0
37        return dfs(root, 0);
38    }
39};
40

Typescript Solution

1// Typescript type definition for a binary tree node.
2type TreeNode = {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6};
7
8/**
9 * Determines if the binary tree has a root-to-leaf path that sums up to the given target sum.
10 * 
11 * @param {TreeNode | null} root - The root node of the binary tree.
12 * @param {number} targetSum - The target sum to find the path for.
13 * @returns {boolean} - True if such a path exists, otherwise False.
14 */
15function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
16  // If the root is null, there is no path, return false.
17  if (root === null) {
18    return false;
19  }
20
21  // Destructure the current node to get its value and its children.
22  const { val, left, right } = root;
23
24  // If the node is a leaf (no left or right children),
25  // Check if subtracting the node's value from the target sum equals 0.
26  if (left === null && right === null) {
27    return targetSum - val === 0;
28  }
29
30  // Recursively check the left and right subtrees reducing the target sum by the current node's value.
31  // Return true if either subtree has a path that sums up to the adjusted target sum.
32  return hasPathSum(left, targetSum - val) || hasPathSum(right, targetSum - val);
33}
34
Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫