Solving tree problems on a mesh-connected processor array

In this paper we present techniques that result in O(√n) time algorithms for computing many properties and functions of an n-node forest stored in an √n × √n mesh of processors. Our algorithms include computing simple properties like the depth, the height, the number of descendents, the preorder (resp. postorder, inorder) number of every node, and a solution to the more complex problem of computing the Minimax value of a game tree. Our algorithms are asymptotically optimal since any nontrivial computation will require Ω (√n) time on the mesh. All of our algorithms generalize to higher dimensional meshes.