Identifying the stateful preorder traversal pattern

The stateful preorder traversal technique can solve a wide variety of binary tree problems. These are generally easy or medium problems where we need to process every node using the aggregated value of some function f over all the nodes in the path from the root node to itself, and also update some state variable shared between all nodes with the aggregated value using some function g as we traverse. In most cases, the final values of the state variables at the end of preorder traversal are the solution to such problems.

If the problem statement or its solution follows the generic template below, it can be solved by applying the stateful preorder traversal technique.