112. Path Sum

Time: O(n)

Space: O(h)

Intuition

DFS: subtract the current node's value from the target. At a leaf, check if the remaining target equals zero. Recurse down both children.

Algorithm

1If root is null, return false.
2If leaf (both children null): return root.val == targetSum.
3Return HasPathSum(root.left, targetSum - root.val) || HasPathSum(root.right, targetSum - root.val).

Example Walkthrough

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

1.Subtract 5->17. Go left: subtract 4->13. Go left: subtract 11->2. Go left: 7!=2 no. Go right: 2==2 .

Output: true

Common Pitfalls

•Do not return true when reaching null - a null node is not a leaf.

112.cs

// Approach: DFS subtracting each node's value from the remaining target sum.
// At each node, reduce target by node.val and recurse into both children.
// A leaf node (no children) returns true only when the remaining sum equals zero,
// confirming the root-to-leaf path sums to the original target.
// Every node is visited at most once — O(n) time. Stack depth equals tree height O(h).
// Time: O(n) Space: O(h)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public bool HasPathSum(TreeNode root, int targetSum)
    {
        if (root == null)
            return false;

        if (root.val == targetSum && root.left == null && root.right == null)
            return true;

        bool left = HasPathSum(root.left, targetSum - root.val);
        bool right = HasPathSum(root.right, targetSum - root.val);

        return left || right;
    }
}

Was this solution helpful?