I guess this is going to be my first post (apart from the contest analysis’) which is not about Number Theory! It’s not about graph either, even though the title has “Tree” in it. This post is actually about Combinatorics.

Prufer code, in my opinion, is one of the most underrated algorithms I have learned. It has a wide range of applications, yet, very few people seem to know about it. It’s not even a hard algorithm! It’s very easy and you should understand it intuitively.

In this post, we will be discussing what is Prufer Code and its conversion to and from a tree. On next post, we will look into some of its application.

Prufer Code: What is it?

Every labeled tree of $N$ nodes can be uniquely represented as an array of $N-2$ integers and vice versa

The linear array representation of a labeled tree is called Prufer Code. In case you are wondering what’s a labeled tree, it’s just a tree with distinguishable nodes, i.e, each node is marked such that they can be distinguished from one another.

Okay, before we move on to how to covert a labeled tree into Prufer Code and vice versa, let me tell you how I came to know about Prufer Code. If you are a problem setter, the story will be helpful to you.

Read More