Path Reconstruction in Barning–Hall Tree

In 1963 F. J. M. Barning and in 1970 A. Hall gave a systematic procedure to generate all primitive Pythagorean triples (PPTs) with help of multiplication of the minimal Pythagorean triple $[3,4,5]$ considered as a vector by matrix series where matrices are taken from a prescribed 3-set of unimodular matrices. This provides a structure of an infinite ternary rooted labeled tree. In this article we establish an algorithm that reconstructs a tree path leading from the root to the primitive Pythagorean triple of interest. Because a triple can lie deeply then efficiency of the algorithm is quite important. The established algorithm has polynomial time complexity with respect to the input length relating to a “size” of PPT.