Understanding the level order column traversal pattern

The level order traversal processes nodes from top to bottom and from left to right and so, the nodes that belong to the same column are always encountered from top to bottom. This makes the level order traversal over columns ideal for solving problems where we need to apply some function on all nodes of a column, one column at a time, from the leftmost column to the rightmost column.

The level order column traversal technique

Consider we are given a binary tree, and for all columns in the tree, we need the aggregated value of a function f (like sum, min, or max of the node values) over all nodes in a column. The aggregates for each column are further aggregated from the leftmost column to the rightmost column using some function g (for example, another sum over columns, or append into a list of column results) to return a single value.