A Note on Naturally Embedded Ternary Trees - Kuba, Markus (The Electronic Journal of Combinatorics, 2011)
In this note we consider ternary trees naturally embedded in the plane in a deterministic way. The root has position zero, or in other words label zero, and the three children of a node with position jZ have positions j-1, j, and j+1. We derive the generating function of embedded ternary trees where all internal nodes have labels less than or equal to j, with jN. Furthermore, we study the generating function of the number of ternary trees of size n with a given number of internal nodes with label j. Moreover, we discuss generalizations of this counting problem to several labels at the same time. We also study a refinement of the depth of the external node of rank s, with 0s2n, by keeping track of the left, center, and right steps on the unique path from the root to the external node. The 2n+1 external nodes of a ternary tree are ranked from the left to the right according to an inorder traversal of the tree. Finally, we discuss generalizations of the considered enumeration problems to embedded d-ary trees.