# Appropiate data structure storing a tree

So I have an input of the type:

Node parent

but the problem is that the nodes and parent aren't given in a specific order starting from root, and I want to build a Trie but I can't because of this aspect, I thought about using a queue with Trie nodes, and when their parent appear I will pop them from the queue, but there is a problem since what if their parents are already in the queue? And I don't know how to solve this problem.. or to solve it efficiently

sample input:
1 0
0 -1
2 1
3 0
4 3


-1 as a parent means it is the root node, observe the order is random.

• As I understand, a trie, also called digital tree, radix tree or prefix tree, is a kind of search tree. More specifically, a trie is an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. It is hard to see how the example input given by you corresponds to a trie. That input just describes a rooted tree with root at node 0. – Apass.Jack Apr 8 at 14:50
• Yeah, but the question is NOT about a Trie, I will build one anyway, the question is about, How to memorize the nodes in the specific order from root to leafs, since that to evrry node is given a parent, how to put it in the Trie if the parent hasn't been already put into the Trie? – C. Cristi Apr 8 at 14:52
• Go through the list, create each node. Go through the list again, add all edges. – ryan Apr 8 at 16:07