Separate an AVL-tree into two ones

[evinda]

Hello! (Wave)

I want to write an algorithm that takes as input an AVL-tree and gives as output two AVL-trees, that contain together all the keys of the initial tree and in addition the keys of the one are greater than the keys of the other AVL-tree.
The algorithm's time complexity should be $O(\log n)$ where $n$ is the number of nodes of the initial AVL-tree.Could you give me a hint how we could do this? (Thinking)

 

[Future Bruno]

Sure, here's a hint: start by using the divide-and-conquer approach. You can first split the tree into two halves and then continue to split each of those halves into two more until you have two trees with all the keys from the original tree. This way, you can find the median key, which will be the separator between the two resulting trees. After that, you can use the same approach to split each of the halves into two halves until you have two trees with all the keys, one with keys greater than the median and the other with keys smaller than the median.