1
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ "I've approached it by initially finding the number of elements" How can you do in $O(logN)$? It seems that you have to traverse the tree what gives $O(N)$. $\endgroup$ – Vladislav Mar 31 '20 at 11:26
  • $\begingroup$ Oh sorry, there was a typo. I did this by checking the size of the subtree at each of the roots - as each node has the size of its subtree rooted at it, hence the number of elements in that tree. So there is no need to traverse the tree. $\endgroup$ – BarTM Mar 31 '20 at 13:18
  • $\begingroup$ Would $O(\log^2 n)$ time suffice? $\endgroup$ – Steven Mar 31 '20 at 14:21
  • $\begingroup$ @Steven no sorry, the algorithm is meant to take in two AVL trees as input and return the median in O(log n) time. $\endgroup$ – BarTM Mar 31 '20 at 14:26
  • $\begingroup$ See also: Find the median in two AVL BSTs in $O(log(n))$, Find the median in two AVL BSTs in $O(log(n))$ $\endgroup$ – greybeard Mar 31 '20 at 14:41

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.