Identifying the reverse sorted traversal pattern

The reverse sorted traversal technique can solve some specific types of binary search tree problems. These are generally easy problems where we need to process every node using the function f in the reverse sorted order (descending) of values of the nodes. We may also need to aggregate all the processed values over a function g in the same order. In cases where the same copy of some data must be shared between all nodes, those variables are created in the calling function or the enclosing scope.

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

Example

Let's consider the following problem as an example to better understand how to identify and solve a problem using the reverse sorted traversal technique.