I'm attempting the problem of finding the median element in two AVL BST's in $O(\log n)$ time. In this problem, we are given two AVLs, with a combined size of $n$ (the distribution across the two trees need not be balanced – it could be that one AVL contains $n-1$ elements, and the other $1$), and the goal is to find the median of the union of the elements in both AVLs.
I am currently trying to come up with an algorithm to solve this. Each node, besides holding its integer value and pointers to its parent and child nodes, holds the subtree size for the subtree rooted at it. I've approached it by initially finding the number of elements $n$ (we assume this to always be odd) via the size of the subtree stored in each AVL tree's root. Let the subtrees be $A$ and $B$, where $A_L$ is the left subtree of $A$ and $A_R$ is the right. I've begun by operating on the AVL tree of a larger size and then comparing $A_L$ and $A_R$'s sizes. With this approach, I am trying to rule out the existence of the median in one of the subtrees, but I'm currently confused on how to do this. Any ideas?