Path Sum

TypeTree
Difficulty
Easy
Last Reviewed12/23/2024

Problem Description

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.

Example 1

Input: [5,4,8,11,null,13,4,7,2,null,null,null,1]

Output: true

Explanation: The binary tree in this example has a root-to-leaf path 5->4->11->2 which sums up to 22, which is equal to the target sum.

Example 2

Input: [1,2,3]

Output: false

Explanation: The binary tree in this example does not have any root-to-leaf path that sums up to the target sum.

Example 3

Input: [1,2]

Output: false

Explanation: The binary tree in this example has only two nodes, and there is no root-to-leaf path to consider.

Solution Overview

Initial Approach

One common approach is to traverse the tree using Depth First Search (DFS) and keep track of the sum of nodes from root to the current node. Check if the current node is a leaf and if the sum matches the target sum. Return True if the target sum is found, else continue the search. Repeat this process for each node in the tree.

Step by Step Solution

  1. Start DFS traversal from the root node with the target sum
  2. At each node, subtract the node's value from the target sum
  3. Check if the current node is a leaf node and if the remaining sum equals 0
  4. If the above condition is met, return True
  5. If the above condition is not met, recursively check the left and right child nodes with the remaining sum

Solution Code

1# Problem: Path Sum
2# Description: 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.
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
13        if not root:
14            return False
15        if not root.left and not root.right:
16            return targetSum == root.val
17        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
18

Solution Walkthrough

Given the binary tree: [5,4,8,11,null,13,4,7,2,null,null,null,1], target sum = 22

Step 1

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7def hasPathSum(root, targetSum):
8    if not root:
9        return False
10    if not root.left and not root.right:
11        return targetSum == root.val
12    return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)

Define the TreeNode class and the hasPathSum function to check if there exists a root-to-leaf path in the binary tree that equals the target sum. Recursively check the left and right subtrees by subtracting the current node's value from the target sum.

State:

Step 2

1# Example Usage
2root = TreeNode(5)
3root.left = TreeNode(4)
4root.right = TreeNode(8)
5root.left.left = TreeNode(11)
6root.left.left.left = TreeNode(7)
7root.left.left.right = TreeNode(2)
8root.right.left = TreeNode(13)
9root.right.right = TreeNode(4)
10root.right.right.right = TreeNode(1)
11targetSum = 22
12print(hasPathSum(root, targetSum)

Create a binary tree based on the given example and calculate if there exists a path from root to leaf with the target sum of 22.

State:

Complexity Analysis

Time Complexity: O(n)

We visit each node in the binary tree once during the traversal, where 'n' is the number of nodes in the tree.

Space Complexity: O(n)

The space complexity is O(n) where n is the number of nodes in the binary tree. This is because we are using recursive calls that consume space on the call stack.

Breakdown:

    Algorithmic Patterns

    Depth-First Search (DFS)

    How it's used: Traversing through all nodes of a tree or graph

    Where in code: Tree traversal problems

    Example: Path Sum, Maximum Depth of Binary Tree

    Recursion

    How it's used: Solving problems by breaking them down into smaller, similar subproblems

    Where in code: Many algorithmic problems

    Example: Fibonacci Series, Factorial Calculation

    Backtracking

    How it's used: Exploring all possible solutions by incrementally building the solution and removing those that fail

    Where in code: Problems with multiple possible solutions

    Example: N-Queens, Subsets

    Common Mistakes

    Mistake 1

    What: Not handling edge cases properly

    Why: Missing edge cases can lead to incorrect results

    How to avoid: Identify all possible edge cases and handle them in your solution

    Mistake 2

    What: Forgetting to check if a node is a leaf node

    Why: Not checking for leaf nodes can cause incorrect summation of paths

    How to avoid: Ensure to check if a node is a leaf node before calculating the path sum

    Mistake 3

    What: Incorrectly updating the path sum in recursive calls

    Why: Updating the path sum incorrectly can lead to wrong results

    How to avoid: Make sure to update the path sum correctly in each recursive call

    Interview Tips

    • Understand the problem requirements clearly before starting
    • Break down the problem into smaller subproblems
    • Consider using recursion to traverse the tree