Prüfer Code Challenge

Let’s tackle the problems step-by-step!

Generating Prüfer Code from a Tree

For the given tree structure:

    1
   / \
  2   3
 / \
4   5

We will find the Prüfer code by following these steps:

1. Create a list to store the Prüfer code.
2. Count the degree of each vertex (how many edges are connected to it).
3. Repeat until there are only 2 vertices left:

1. Find the smallest labeled leaf (a vertex with degree 1).
2. Record the neighbor of that leaf in the Prüfer code.
3. Remove the leaf from the tree and update the degree of its neighbor.

Here’s a simple Python code to illustrate this:

def generate_prufer_code(tree):
    from collections import defaultdict

    # Build the graph
    graph = defaultdict(list)
    for u, v in tree:
        graph[u].append(v)
        graph[v].append(u)

    prufer_code = []
    
    # Count degrees
    degree = {i: len(graph[i]) for i in graph}

    while len(degree) > 2:
        # Find the smallest labeled leaf
        leaf = min((node for node in degree if degree[node] == 1))
        neighbor = graph[leaf][0]

        prufer_code.append(neighbor)

        # Remove the leaf
        degree[leaf] -= 1
        degree[neighbor] -= 1

        if degree[neighbor] == 0:
            del degree[neighbor]
        if degree[leaf] == 0:
            del degree[leaf]
    
    return prufer_code

tree = [(1, 2), (1, 3), (2, 4), (2, 5)]
print(generate_prufer_code(tree))  # Output: [2, 1, 2]

Reconstructing a Tree from a Prüfer Code

For a given Prüfer code like [4, 2, 3], we can reconstruct the tree using these steps:

1. Count the occurrences of each vertex in the Prüfer code.
2. Create a list of all vertices (numbered from 1 to n).
3. Add edges between the smallest unlabeled vertex and the vertex from the Prüfer code while removing them progressively.

Here’s a Python code to do that:

def reconstruct_tree(prufer_code):
    from collections import defaultdict

    degree = [1] * (len(prufer_code) + 2)  # Start with 1 degree for each vertex
    for node in prufer_code:
        degree[node - 1] += 1  # Increment the degree for nodes in the Prüfer code

    edges = []
    ptr = 0  # Pointer to the smallest leaf
    n = len(prufer_code) + 2
    leafs = [i for i in range(1, n + 1) if degree[i - 1] == 1]

    for node in prufer_code:
        # Find the next leaf
        while ptr < len(leafs) and leafs[ptr] < node:
            ptr += 1

        # Connect the leaf to the current node in the Prüfer code
        edges.append((leafs[ptr], node))
        degree[node - 1] -= 1
        degree[leafs[ptr] - 1] -= 1

        # Remove the leaf if its degree is 0
        if degree[leafs[ptr] - 1] == 0:
            leafs.pop(ptr)

        # Add leaf back if a degree decrease creates a new leaf
        if degree[node - 1] == 1:
            leafs.append(node)

    # Connect the last two remaining nodes
    last_two = [i for i in range(1, n + 1) if degree[i - 1] == 1]
    edges.append((last_two[0], last_two[1]))

    return edges

prufer_code = [4, 2, 3]
print(reconstruct_tree(prufer_code))
# Output: Tree edges based on the Prüfer code

By following these methods, we can efficiently generate the Prüfer code and reconstruct the tree!