51. Path Sum

A large-scale platform (such as a financial system, recommendation engine, or monitoring service) represents decision flows and hierarchical computations using binary trees.

Each node in the tree represents:

• a transaction value
• a scoring metric
• or a decision weight

The system needs to validate whether a specific cumulative value can be achieved by following a valid path from the root to a terminal node.

This is particularly useful in:

• validating transaction chains
• checking scoring thresholds
• analyzing decision outcomes

The system defines a valid path as a path starting from the root and ending at a leaf node (a node with no children).

The platform receives:

• a binary tree (root)
• a target value (targetSum)

It must determine whether any root-to-leaf path exists such that the sum of node values equals the target.

This is a common practice coding problem frequently asked in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Given the root of a binary tree and an integer targetSum, return:

• true if there exists a root-to-leaf path where the sum equals targetSum
• false otherwise

Input Format

• root: root of the binary tree
• targetSum: integer

Each node:

TreeNode { int val; TreeNode left; TreeNode right;}

Output Format

• Boolean (true or false)

Examples

Constraints

• 0 ≤ number of nodes ≤ 100,000
• -1000 ≤ Node.val ≤ 1000
• -1000 ≤ targetSum ≤ 1000