0

I have two AVL trees filled with numbers from a set. The information stored in every node is both the value of the node itself and the size of the corresponding subtree. The question is how can I (in an optimal time complexity) find the nth value of the sorted array containing all the items in the AVL trees (basically, the nth smallest number).

My approach would be to do some kind of binary search regarding the sizes of the subtrees, but the fact that there are two makes it a little bit more difficult. Would it be inefficient to firstly combine the two AVL trees? What would be your approach?

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
Flavi Burcã
  • 3
  • 1
  • It's a slight modification of the problem of finding the k-th element in two sorted arrays (that might have different size). See, for example, https://stackoverflow.com/q/4607945/56778. See also https://stackoverflow.com/q/40473890/56778 – Jim Mischel Jan 17 '23 at 19:13
  • Yes, it seems like it! Thanks! I did not find those questions at first. – Flavi Burcã Jan 17 '23 at 22:22

0 Answers0