Full Text: PDF
DOI: 10.23952/cot.2027.14
Received April 15, 2026; Accepted March 27, 2026; Published online October 3, 2026
Abstract. We obtain a generating series whose coefficients are polynomials that, for a given positive integer n, encode the depth at which the various list entries appear as labeled nodes in the binary trees obtained by QuickSorting permutations of the list consisting of one copy of each of the first n non-negative integers. Extracting the appropriate coefficients yields information in the form of “node distribution polynomials” that encode the distribution of list entries that appear at different depths, and “depth distribution polynomials” that encode the distribution of depths at which a given list entry appears. These yield formulas for the number of times a given list entry appears at a given depth, the total number of list entries that appear at a given depth, and consequently the average number of list entries that appear at a given depth taken over all n! permutations.
How to Cite this Article:
D.M. Bradley, J. Thiel, Polynomials that encode depth and node information for the binary trees created by quicksort, Commun. Optim. Theory 2027 (2027) 14.