Identifying Binary Search Trees from their Prufer Sequence

Question

If you ignore its root, a Binary Search Tree generated by some permutation of $\{1, \ldots, n\}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found that there are A000245 distinct Prufer sequences.

import itertools

def generate_tree(l):
    '''Return the root and a set of edges'''
    if len(l) == 0:
        return None, None
    if len(l) == 1:
        return l[0], set()
    left_root, left_edges = generate_tree([x for x in l if x < l[0]])
    right_root, right_edges = generate_tree([x for x in l if x > l[0]])
    edges = set()
    if left_root is not None:
        edges.add((left_root, l[0]))
        edges.update(left_edges)
    if right_root is not None:
        edges.add((l[0], right_root))
        edges.update(right_edges)
    return l[0], edges

def pruffer_sequence(edge_set):
    degrees = {}
    for v1, v2 in edge_set:
        degrees[v1] = degrees.get(v1, 0) + 1
        degrees[v2] = degrees.get(v2, 0) + 1
    r = []
    while len(edge_set) > 1:
        smallest_leaf = min([v for v in degrees.keys() if degrees[v] == 1])
        degrees[smallest_leaf] -= 1
        for e in edge_set:
            if smallest_leaf in e:
                edge_set = edge_set - {e}
                neighbor = [v for v in e if v != smallest_leaf][0]
                degrees[neighbor] -= 1
                r.append(neighbor)
                break
    return r

for number_of_vertices in range(2, 10):
    R = set()
    for l in itertools.permutations(range(number_of_vertices)):
        root, edge_set = generate_tree(l)
        R.add( tuple( pruffer_sequence(edge_set) ))
    print number_of_vertices, len(R)

Is there some way to characterize a BST by its Prufer sequence without first calculating its tree?

Answer 1

Is there a reason you chose to take the BST of the permutations? There are multiple ways to uniquely represent a permutation as a tree, where you would end up with $n!$ different Prufer sequences. Categorizing such sequences might be more interesting.

But in any case, I couldn't find a way to enumerate without iterating all the $n!$ permutations. I tried to find a bijection between Prufer sequences and something counted by the difference of Catalan numbers $C_n-C_{n-1}$, but to no avail. I was however, able to speed up your code.

Given two permutations $p_1, p_2 \in S_n$

$$ \text{Prufer}(p_1) \;\;\;= \;\;\; \text{Prufer}(p_2) \\ \Longleftrightarrow \\ \text{Tree}(p_1) \;\;\; = \;\;\; \text{Tree}(p_2) \\ \Longleftrightarrow \\ \text{Edges}(\text{BST}(p_1)) \;\;\; = \;\;\; \text{Edges}(\text{BST}(p_2)) \\ $$ So you only need to find the Prufer sequence when you come across a new edge set. Also, if you actually construct the BST, you can find the Prufer sequence in linear time. Here is my python code (takes 6 seconds rather than 18).