Path Sum

Convert Sorted Array to Binary Search Tree

Remove Nth Node From End of List

Determine whether a binary tree has a root-to-leaf path whose values sum to a target.

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

A leaf is a node with no children. A path must start at the root and end at a leaf — it cannot stop partway down.

**Input / output**
- Input: `root: TreeNode`, `targetSum: int` (JSON test fixture for `root` is a LeetCode-style level-order array, e.g. `[5,4,8,11,null,13,4,7,2,null,null,null,1]`, with `null` for a missing child)
- Output: `boolean`

## Example
```json
Input: {"root":[5,4,8,11,null,13,4,7,2,null,null,null,1],"targetSum":22}
Output: true
```
(5 -> 4 -> 11 -> 2 sums to 22.)

## Constraints
- 0 <= number of nodes <= 5,000
- -1,000 <= node value <= 1,000
- -1,000 <= targetSum <= 1,000

## Follow-up
Can you solve it iteratively with an explicit stack instead of recursion, tracking the running sum alongside each node?

The key pattern is: root-to-leaf DFS that carries a running remaining-sum down the tree instead of accumulating a total up. Identify the state and invariant before coding.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(n) — every node is visited at most once. Space: O(h) for the recursion stack, where h is the tree height (O(n) worst case on a skewed tree).

All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real TreeNode structural-type support the judge added for the rest of the linked-list/tree track.