DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Path Sum - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

# 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 not root:
            return False
        if not root.left and not root.right:
            return root.val == targetSum
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

Complexity Analysis

Here, n is the number of nodes, and h is the height of the binary tree.

  • Time Complexity: O(n)
    • Each node is visited during traversal.
  • Space Complexity: O(n)
    • Stack space: O(h) — for the recursion stack.
      • In the best case (a balanced tree), h = log n.
      • In the worst case (a skewed tree), h = n, so the recursion stack uses O(n) space.