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.

  • $\begingroup$ 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. $\endgroup$ – John L. Apr 8 '19 at 14:50
  • $\begingroup$ 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? $\endgroup$ – C. Cristi Apr 8 '19 at 14:52
  • $\begingroup$ Go through the list, create each node. Go through the list again, add all edges. $\endgroup$ – ryan Apr 8 '19 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.