Katkat
Back

Binary Tree Path Sum

SalesforceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Determine if a binary tree contains a root-to-leaf path whose node values add up to a given target sum.

Problem Statement

Given the root of a binary tree and an integer target_sum, determine whether there exists a root-to-leaf path such that summing all the node values along the path equals target_sum.

A leaf is a node with no children (both left and right child pointers are None). An empty tree contains no paths, so it should return False.

Interface

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
    pass

Examples

Example 1

Input: 
        5
       / \
      4   8
     /   / \
    11  13  4
   /  \      \
  7    2      1
target_sum = 22

Output: True
Explanation: The root-to-leaf path 5 -> 4 -> 11 -> 2 sums to 5 + 4 + 11 + 2 = 22.

Example 2

Input: 
    1
   / \
  2   3
target_sum = 5

Output: False
Explanation: Path 1 -> 2 sums to 3, and path 1 -> 3 sums to 4. Neither equals 5.

Example 3

Input: root = None, target_sum = 0
Output: False
Explanation: Because the tree is empty, there are no root-to-leaf paths.

Constraints

  • The number of nodes in the tree is in the range [0, 10_000].
  • -1_000 <= TreeNode.val <= 1_000
  • -100_000 <= target_sum <= 100_000

Edge Cases to Consider

  • Empty tree (root is None): should return False, even if target_sum == 0.
  • Single node tree: valid leaf only if root.val == target_sum.
  • Negative values: node values or target sums can be negative, so values do not strictly increase along paths.
  • Unbalanced or skewed trees (e.g., linked list shape): recursion depth may reach O(n).

Hints

Hint 1

A node is only a leaf if both its left and right children are None; be careful not to terminate early at a node with only one child.

Hint 2

Think recursively: if you are at node `curr`, check if either subtree contains a path summing to `target_sum - curr.val`.

Hint 3

For an iterative solution, use a stack or queue that stores pairs of `(current_node, remaining_sum)`.

Follow-up questions

  • How would you return all root-to-leaf paths that match the target sum rather than just a boolean?
  • How would you modify the solution if the path does not need to start at the root or end at a leaf, but can start and end at any node moving downward?
  • If the tree is given directly as a level-order array (e.g., `[5, 4, 8, 11, None, 13, 4]`), how would you solve this without converting the array into pointer-based TreeNode objects?