tree.py

def next_node_value(i, n):
    if i % 2 == 0:
        return i // 2
    else:
        return n - (i // 2) - 1

def f(array, edgearray, i, n):
    if i >= n:
        print(n, array)
        raise 0
    
    # prune
    if i >= 2 and (n - (i // 2)) not in edgearray:
        return

    v = next_node_value(i, n)

    for p in range(n):
        if array[p] != -1:
            continue

        # try to put v on the p-th node
        neighbors = []
        if p != 0:
            neighbors.append((p - 1) // 2)
        if 2 * p + 1 < n:
            neighbors.append(2 * p + 1)
        if 2 * p + 2 < n:
            neighbors.append(2 * p + 2)
        
        new_edges = [ abs(array[neighbor] - v) for neighbor in neighbors if array[neighbor] != -1 ]

        if len(set(new_edges)) < len(new_edges):
            continue

        if any(edge in edgearray for edge in new_edges):
            continue
    
        # OK, add it 
        array[p] = v
        f(array, edgearray + new_edges, i+1, n)
        
        # failed, revert
        array[p] = -1

def g(k):
    for n in range(k):
        try:
            f([-1] * n, [], 0, n)
        except:
            pass

g(20)