Identifying the stateless root to leaf path pattern

The stateless root-to-leaf path technique can only solve a certain type of binary tree problem. These are generally easy or medium problems where we need to find the aggregated value of a function f over all nodes in every root-to-leaf path. For most problems, we need to further aggregate these aggregated values over another function g.

The stateless solution works by incrementally aggregating values over function f by passing the aggregated value of a path down from the parent to child nodes, computing the root-to-leaf aggregate on reaching a leaf node, and returning and merging all root-to-leaf path aggregates using the function g on the way up.

If the problem statement or its solution follows the generic template below, it can be solved by applying the stateless root-to-leaf path technique.

Example