I want to merge two trie structures, but the best complexity I can think of is
Get list of values from other trie: O(n), n is number of nodes in trie. Insert all values from list intro target trie: n * O(m), m is length of key Taking into account, that at worst, the key is of size n, isn't the complexity of merge O(n^2)?
Is there any better way of doing it?
The complexity is going to be O(N+M). You need two iterators (tree node pointers) both start on the root node of the respective trees.
You look at the children if a child is in only present in one of the iterators then you just copy that child into the result (if you can move the child directly (assign the pointer) even better). If a child is present on both sides call the function recursively on the respective children.
This way you only spend time merging the nodes that are ambiguous and you can copy/move entire subtrees in one go.
If you run your original idea the complexity is going to be O(N*M) where N is the number of entries and m is the average length of an entry. You don't get O(N^2) because if all the nodes are for a single entry (your worst case) you still need to copy that entry only once.