# Unite a forest if you know each tree's parent

I have a forest of Tries, each forest[i] is a Trie. forest[0] contains the root node to all the others. I want to recursively unite all of the Tries if I know each Trie's parent.. how can I do that?

This is my data structure and this is how I am using it.

typedef struct trie
{
int id;
int parent;
struct trie *child;
struct trie *sibling;
} *Trie;
Trie *forest;


EDIT with photos:

We have 2 tries here:

If node 4 which is the "root" of the right Trie had the parent 9 for example, I would like to "unite" 9 to 4 and get the bigger Trie.

I would like to implement a function

Trie uniteForest(Trie root, Trie *forest, int id)
{
// do stuff
}


That returns me the final "Trie".

• I'm not sure what you're asking. What do you mean by "unite"? Do you just make one node a child of the other? Also what is a Trie's parent? Is this different than the root? Also, if these are specifically Trie's then uniting them is non trivial if you want to maintain properties of a Trie. For instance when merging a trie of {his, her, him} and a trie of {hero, heavy, hippy}. Could you provide a small picture/diagram of an example of what you're looking for? – ryan Apr 9 '19 at 16:21
• @ryan yeah i will provide pictures in 10 mins – C. Cristi Apr 9 '19 at 16:25
• @ryan Check the edit! I hope my question is more clear now – C. Cristi Apr 9 '19 at 16:56
• Also, can you specifically define what it means to "unite" a node A and a node B? This might help clear up some confusion as I don't quite get it from this example. – ryan Apr 9 '19 at 17:39
• I mean to define "unite" in general, not for this example. The definition should be something like this definition of union: "Union(x,y) uses Find to determine the roots of the trees x and y belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other." – ryan Apr 9 '19 at 17:48