Path Sum

View Path Sum on LeetCode

Statistics

Time Complexity
O(n) - Every node in the tree is visited, resulting in the O(n) time complexity.

Space Complexity
O(n) - The algorithm makes n recursive calls, filling the stack with temporary variables for each recursive call, resulting in the O(n) space complexity.

Runtime Beats
99.61% of other submissions

Memory Beats
82.27% of other sumbissions

Explanation

The algorithm works by using depth-first search and recursively searching one entire branch (root to leaf/NULL) before moving to the next possible path.

The algorithm checks the following conditions:

1. if root == None: If the root is None, then the targetSum was not met on this branch, and we return False.
2. elif root.left == None and root.right == None: If both the left and right nodes are None, a leaf node is found, so if the remaining target sum is equal to the node’s value, there is a path that sums to the target.
3. else: Explore the left and right branches of the current node, and subtract the node’s value from the target sum. Doing this allows for multiple paths to be taken without passing a new variable and instead updating the target sum to the remaining amount.

Data Structure and Algorithm Used

Binary Tree - A rooted tree where every node has at most two children, the left and right children.

Depth-First Search - An algorithm for traversing a tree data structure. The algorithm begins at the root node and searches until it can not continue any deeper. Once at the deepest point, the algorithm works backward until all the nodes have been visited.

Visual Examples
Depth-first search being performed on a tree, click to view

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root == None:
            return False

        elif root.left == None and root.right == None:
            return targetSum == root.val

        else:
            return self.hasPathSum( root.left, targetSum - root.val) or \
                self.hasPathSum(root.right, targetSum - root.val)