# Why would we want to convert a forest or generic tree to binary tree?

Why sometimes we would want to convert generic trees or forests into a binary tree? And what's the main principle behind this convertion?

• what kind of conversion are you thinking of? Jan 11, 2023 at 11:30
• @user253751 how many conversions are there? I know just one kind of conversion that converts a generic tree (or a forest) to equivalent binary tree. Jan 11, 2023 at 12:19
• equivalent in what sense? I could say the binary tree is not equivalent to the non-binary tree because they have different degrees at their vertices, and this makes them different. Perhaps one is a minimal spanning tree and the other one isn't. And a forest may be unconnected while a tree (binary or not) is connected which is also a very big difference. Jan 11, 2023 at 12:20
• @user253751 that's exactly what I'm asking. When converting one tree to another, there must be something that should remain the same. Feb 13, 2023 at 6:15
• and that depends on the application! Feb 13, 2023 at 11:39

Such a conversion can occur when trying to represent an abstract tree on a computer.

If you consider an edge between a node and one of its children, it is natural to implement it as a memory pointer. However, on a generic tree, that would mean that each node could contain any number of memory pointers. This is not acceptable.

In an usual representation, each node $$x$$ contains a linked-list containing all children $$[y_1, y_2, …, y_k]$$ of the node $$x$$. However, in terms of memory pointers, that means that $$x$$ contains a pointer to its first child $$y_1$$, and each $$y_i$$ contains a pointer to the next sibling $$y_{i+1}$$.

In such an implementation, each node contains exactly 2 pointers: one to its first child and one to its next sibling. This is a binary tree.

When considering a forest, the idea is exactly the same, since the forest could be seen as a linked-list of the roots of the trees in the forest.

As an example, you could use the following structures:

• In C:
struct node{
int value;
struct node* first_child;
struct node* next_sibling;
};

• In OCaml (here, the next_sibling pointer is not explicit, since we are using the list type):
type tree = Node of int * tree list
type forest = tree list

• When you say, "this is not acceptable", is it because the static nature of arrays in languages like C? Can't we implement it with dynamic array? Feb 13, 2023 at 6:12
• You are right that this is possible, but that would potentially use a lot of memory per node. Feb 13, 2023 at 10:08

Binary trees have nodes of constant size, using two links: to the first descendant and to the sibling. This makes allocation easier.

• A sibling link allows any arity of tree to be represented. A binary tree has a left descendant and a right descendant. Feb 13, 2023 at 11:46
• @user253751: yes of course. I don't know why I made this answer ?!
– user16034
Feb 13, 2023 at 11:57