There is a follow up to this question. Given two (balanced) binary search trees, where the first BST has N nodes and the second has M nodes, how would you merge both trees in linear time and constant space?

(The solution is here if you are interested https://stackoverflow.com/questions/7540546/merging-2-binary... )