Path Sum in Binary Tree

Q: What is the time complexity of Path Sum in Binary Tree?

O(n). Each node is visited once in the recursive traversal, resulting in linear time proportional to the number of nodes.

Q: What pattern does Path Sum in Binary Tree use?

The Pattern: DFS (Recursive State Exploration on Trees) The Heuristic: When searching for a path with a specific property in a tree, recursively reduce the problem by updating the target state and check conditions at leaf nodes, using the call stack to implicitly track the path.

Easy DFS

Problem

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, and false otherwise.

The number of nodes in the tree is in the range [0, 5000]
−1000 ≤ Node.val ≤ 1000
−1000 ≤ targetSum ≤ 1000

Example

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

Output: true

The algorithm explores paths starting from the root. For example, one path is 5 -> 4 -> 11 -> 2, which sums to 22. The recursion subtracts the current node's value from targetSum and explores left and right subtrees. When it reaches a leaf node, it checks if the remaining targetSum equals the leaf's value. If yes, it returns true, indicating a valid path exists. If no path matches, it returns false.

Approach

Straightforward Solution

A brute-force approach would explore all root-to-leaf paths, summing values along each path. This can be done with DFS, but without pruning, it explores all paths, which is acceptable here but can be inefficient for large trees.

Core Observation

The problem reduces to checking if any root-to-leaf path sums to targetSum. This naturally suggests a depth-first traversal where the targetSum is decremented by the current node's value at each step.

Path to Optimal

Preview

The key insight is to decrement targetSum as the recursion descends. When a leaf node is reached, checking if the remaining targetSum equals the leaf's value immediately confirms if a valid path exists…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS that at each node subtracts the node's value from targetSum and recursively checks left and right children. If the node is a leaf, return whether the remaining targetSum equals the node's value…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited once in the recursive traversal, resulting in linear time proportional to the number of nodes.

Space

O(h)

The recursion stack depth is at most the height of the tree, which is O(h). In the worst case (skewed tree), h can be O(n), but for balanced trees, h is O(log n).

Pattern Spotlight

DFS (Recursive State Exploration on Trees)

When searching for a path with a specific property in a tree, recursively reduce the problem by updating the target state and check conditions at leaf nodes, using the call stack to implicitly track the path.

Solution

Python

1class 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))

Step-by-Step Solution

Return False Immediately for Empty Tree

3if not root:
4    return False

Objective

To handle the edge case where the input tree is empty, returning false since no path exists.

Key Insight

An empty tree has no root-to-leaf paths, so the answer must be false. This early return prevents unnecessary recursion and handles a critical boundary condition cleanly.

Interview Quick-Check

State & Boundaries

Check if the root is None to handle the empty tree edge case.

Common Pitfalls & Bugs

Failing to handle the empty tree can cause errors or incorrect results.

Check Leaf Node and Compare Value to Remaining TargetSum

To determine if the current node is a leaf and if its value matches the remaining targetSum, indicating a valid path.

Recursively Explore Left and Right Subtrees with Updated TargetSum

To recursively check if either the left or right subtree contains a root-to-leaf path summing to the updated targetSum after subtracting the current node's value.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 7 Critical

return root.val == targetSum

Return whether the leaf node's value equals the remaining targetSum.

This comparison confirms if the current root-to-leaf path sums exactly to targetSum, which is the problem's success condition.

Line 10 Critical

self.hasPathSum(root.right, targetSum - root.val))

Recursively check the right subtree with updated targetSum and return true if either subtree has a valid path.

Using logical OR combines the results from both subtrees, ensuring the function returns true if any root-to-leaf path matches the target sum.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does the algorithm check for leaf nodes before comparing the remaining targetSum?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Path Sum in Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Path Sum in Binary Tree drill

or drill a free problem

1	`class Solution:`
2	`def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:`
3	`if not root:`
4	`return False`
5
6	`if not root.left and not root.right:`
7	`return root.val == targetSum`
8
9	`return (self.hasPathSum(root.left, targetSum - root.val) or`
10	`self.hasPathSum(root.right, targetSum - root.val))`