Complete Binary Spanning Trees of the Eight Nearest Neighbor Array

Complete binary spanning trees of an n x n array of processors with an eight nearest neighbor interconnection pattern exist for a limited value of n. These spanning trees provide a fast route to accumulate information from all processors of the array, and allow certain problems to be solved as efficiently on an eight-neighbor array as on a tree-structured array. The condition under which complete binary spanning trees of a square array may exist is determined. This condition shows that complete binary spanning trees of an n x n eight-neighbor array exist only for n ≪ = 13. It is also observed that for n ≪ = 6, leaf nodes of these spanning trees lie on the periphery of the array.