Identifying the stateful postorder traversal pattern

The stateful postorder traversal technique is very versatile and can solve a wide variety of binary tree problems. These are generally easy or medium problems where we need to process every node using an aggregated value of some function f applied to its left and right subtrees, and also update some state variable shared between all nodes with the aggregated value as we traverse. A combination of the aggregated value at the root and the state variables is generally the solution to these problems.

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

Template:

Given a binary tree, process every node using the aggregated value of a function f applied to its left and right subtrees. The processing of a leaf node or a null reference should be trivial, meaning it should have a known solution.

Example

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

Problem statement: Given the root of a binary tree, write a function to calculate and return the diameter of this tree

The diameter of a binary tree is the longest distance between any two nodes in the tree, whether or not they pass through the root. The distance here is defined by the number of edges in the path.

Find the diameter of a binary tree.