Given two 2-3 trees I would like to merge them in $O(n_1+n_2)$
I've solved before that if I get an ordered list then I can turn it into 2-3 tree in $O(n)$.
My questions is how can I turn two trees into one ordered list in $O(n_1+n_2)$ and then I know how to solve this.

  • $\begingroup$ Looks like an inorder traversal of a 2-3 tree is O(n). So just traverse both trees inorder and create your combined ordered list by adding the smallest element from the two trees. Should be O(n1+n2) to create the combined list. $\endgroup$ – Bobby Durrett Dec 15 '20 at 22:27

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.