A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗
Rong Lin, Stephan Olariu · International Journal of Parallel Emergent and Distributed Systems · 1995
Encoding the shape of a tree is a basic step in a number of algorithms in integrated circuit design, automated theorem proving, and game playing. We propose a simple cost-optimal encoding algorithm for ordered trees and show that our encoding can be used to obtain an optimal Breadth-First traversal of ordered trees. Specifically, with an n-node ordered tree as input our algorithms run in O(logn) time using O(n/logn) processors in the EREW-PRAM model of computation. We then show that the Breadth-First algorithm can be used to produce new encodings of binary and ordered trees.