Identifying the sorted traversal pattern

The 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 sorted order (ascending) 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 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 sorted traversal technique.

Problem statement: Given a binary search tree, find the minimum absolute difference between the values of any two different nodes in the tree.