A Correspondence between Stack Permutations and Binary Trees via Hille Encoding

DOI: https://doi.org/10.62517/jbdc.202501121

Author(s)

Kelan Liu, Lijuan Du*

Affiliation(s)

College of Applied Science and Technology, Beijing Union University, Beijing, China *Corresponding Author.

Abstract

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.

Keywords

Encoding; Binary Trees; Stack Permutations; Correspondence

References

[1] Knott, Gary D. “A Numbering System for Binary Trees.” Communications of the ACM, vol. 20, no. 2, ACM New York, NY, USA, 1977, pp. 113–15. [2] Hille, Reinhold Friedrich. “Stack Permutations and an Order Relation for Binary Trees.” Working Paper 82-8, University of Wollongong, 1982. [3] Flajolet, Philippe, and Robert Sedgewick. Analytic Combinatorics. cambridge University press, 2009. [4] Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Pearson Education India, 2011. [5] Amir Dembo, Thomas M Cover, and Joy A Thoma. “Information Theoretic Inequalities.” IEEE Transactions on Information Theory, vol. 37, no. 6, IEEE, 1991, pp. 1501–18. [6] Munro, J. Ian, and Venkatesh Raman. “Succinct Representation of Balanced Parentheses and Static Trees.” SIAM Journal on Computing, vol. 31, no. 3, SIAM, 2001, pp. 762–76. [7] Blass, Andreas. “Seven Trees in One.” Journal of Pure and Applied Algebra, vol. 103, no. 1, Elsevier, 1995, pp. 1–21. [8] Fiore, Marcelo, and Tom Leinster. “Objects of Categories as Complex Numbers.” Advances in Mathematics, vol. 190, no. 2, Elsevier, 2005, pp. 264–77. [9] Kitaev, Sergey, and Philip B. Zhang. “Non-Overlapping Descents and Ascents in Stack-Sor Permutations.” Discrete Applied Mathematics, vol. 344, Elsevier, 2024, pp. 112–19. [10] Filip Sieczkowski, Sergei Stepanenko, Jonathan Sterling, and Lars Birkedal. “The Essence of Generalized Algebraic Data Types.” Proceedings of the ACM on Programming Languages, vol. 8, no. POPL, ACM New York, NY, USA, 2024, pp. 695–723. [11] Opler, Michal. “An Optimal Algorithm for Sorting Pattern-Avoiding Sequences.” 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2024, pp. 689–99.