Generic Trees (N-ary Trees)

Generic trees can have more than 2 children(in this case A has 6 children) unlike binary tree which has maximum 2 children.

We can represent the above tree as:

Since we are not using all the pointers in all the cases, there is a lot of memory wastage. Another problem is that we do not know the number of children for each node in advance.

Representation of Generic Trees

The above tree can be represented as below:

If we have a link between children then we do not need extra links from parent to all children(thus A is pointing to only B). This is because we can traverse all the elements by starting at the first child of the parent.

This representation is sometimes called first child/ next sibling representation.

Note: Since we are able to convert any generic tree to binary representation; in practice we use binary trees. We can treat all generic trees with a first child/ next sibling representation as binary trees.