A number of combinatorial objects--labeled trees, allowable pairs of input-output permutations for priority queues, factorizations of an n-cycle into transpositions, and parking functions--are all enumerated by the same formula: n^n-2. A series of bijections--some of them related--have been constructed between two or more of these. Here we introduce and prove a direct bijection between priority queue allowable pairs and labeled trees that has an additional property not present in previous direct bijections: our bijection maps increasing sequences in the output permutation of the priority queue allowable pair to leaves in the tree. This gives us a full understanding of the underlying tree structure of priority queue allowable pairs. For instance, we could use this understanding to construct the analogue of a Prufer code for allowable pairs. This is joint work with A. Yong.