Positional Prüfer Sequences: Encoding Ordered Trees in O(n)

June 20, 2026 · Anandhu P Shaji · Research Paper

In 1918, Heinz Prüfer proved Cayley's formula $n^{n-2}$ by establishing a bijection between labeled trees on $n$ vertices and sequences of length $n - 2$ over the alphabet $\{1, 2, \dots, n\}$. While classical Prüfer sequences remain fundamental in algebraic graph theory and network generation, they apply strictly to unordered, unrooted trees.

In theoretical computer science, compiler abstract syntax trees (ASTs), DOM hierarchies, XML schemas, and hierarchical decision processes are ordered rooted trees: the relative sibling order matters, and the root is fixed.

In our work submitted to Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2026), we introduce the Positional Prüfer Sequence (PPS): a bijective encoding that maps any ordered rooted labeled tree on $n$ vertices to an integer sequence of length $n - 1$ in optimal $\mathcal{O}(n)$ time.

The Positional Prüfer Formulation

Classical Prüfer encoding repeatedly removes the leaf with the smallest label and appends its neighbor to the code. However, in an ordered tree, removing arbitrary leaves based solely on numerical label disrupts sibling positioning.

Instead of using global minimum labels across the entire tree, PPS processes leaves through an ordered bottom-up frontier:

• Leaves are retired in strictly defined left-to-right positional order relative to their parent subtrees.
• For each retired node $v$, we record a composite tuple: the parent label $p(v)$ paired with the 0-indexed sibling rank $r(v)$.
• By interleaving parent references and relative sibling offsets, the total sequence length is bounded to exactly $n - 1$ elements.

Optimal $\mathcal{O}(n)$ Encoding and Reconstruction

Naive implementations that search for frontier leaves at each step require $\mathcal{O}(n \log n)$ or $\mathcal{O}(n^2)$ time. We designed a linear-time encoder using an in-degree counter combined with a two-pointer frontier queue:

def encode_pps(tree: OrderedTree) -> List[Tuple[int, int]]:
    n = len(tree.nodes)
    degrees = tree.compute_out_degrees()
    leaf_queue = tree.collect_initial_leaves()
    sequence = []

    while len(sequence) < n - 1:
        leaf = leaf_queue.popleft()
        parent, rank = tree.parent_of(leaf), tree.sibling_rank(leaf)
        sequence.append((parent, rank))
        degrees[parent] -= 1
        if degrees[parent] == 0:
            leaf_queue.append(parent)

    return sequence

The Navigation Index: $\mathcal{O}(1)$ Structural Queries

A common limitation of compact tree encodings (such as balanced parentheses or DFUDS) is that querying the $k$-th child or computing parent pointers requires traversal or auxiliary rank/select structures that introduce significant space overhead.

We augment the Positional Prüfer Sequence with a Navigation Index (NI) of size $\mathcal{O}(n)$ words. By exploiting the recurrence of parent occurrences in the PPS, the Navigation Index answers:

• get_parent(v) in $\mathcal{O}(1)$ time.
• get_kth_child(v, k) in $\mathcal{O}(1)$ time.
• subtree_size(v) in $\mathcal{O}(1)$ time.

Comparative Summary

← Back to all blog posts