A Correspondence between Stack Permutations and Binary Trees via Hille Encoding

This paper systematically investigates the bijective or isomorphic construction problem between stack permutations and binary tree, with a focus on the equivalence and differences between Hille codes and stack codes. Through constructive proofs, we correct algorithmic errors in the original literature and rigorously demonstrate the equivalence between stack codes and Hille codes in the bijective sense. Furthermore, we analyze the intersection size of Hille codes and stack codes, revealing that when the number of binary tree nodes , the overlapping portion constitutes less than half of the total cases. Additionally, we provide precise upper and lower bounds for the effective length of Hille codes, proving that their maximum value is and showing that the binary tree structure achieving this bound is unique. These results offer new tools and perspectives for the study of stacks and binary trees, while also laying a foundation for subsequent algorithm design and combinatorial optimization.