The statement sais the following

Design a function to partition an AVL tree such that, given an AVL tree and a key $x$, it returns two AVL trees, one containing the keys lower or equal than $x$, and the other containing the remaining keys. The complexity must be better than $\mathcal{O}(n)$ (being $n$ the cardinality of the tree).

My attempt is the following recursive algorithm (in pseudo code, so notation abuse is probable).

split(T x, Node root, Node link, Node lower){ if(root.key <= x){ if(lower.isEmpty()) lower=BinaryTree(root.left,root,null); else link.right = BinaryTree(root.left,root,null); link = root; if (root.key< x) split(x,root.right.root,link,lower); } else split(x,root.left.root,link,lower); }

if I am not mistaken, the algorithm returns a binary search tree (but possibly not balanced) whose keys are the ones in the original tree lower of equal than $x$. An analogous one can be done to build the other tree.

So, the question is how to balance both trees without icreasing the current $\mathcal{O}(\log n)$ complexity.


The strategy was wrong. Its better to distinguish cases depending on $x>\text{root}$ or $x\leq \text{root}$. Building the "higher tree" in the first case and the "lower tree" otherwise. For details about balancing take a look here (same question in a more specific stack exchange forum).


An alternate but easy solution is to search for key x and create two sorted lists $S$ and $L$ where $S$ contains all elements les than $x$ and vice-versa for $L$, which can be done in linear time.

Now create a perfect binary search tree on this. If the elements are already sorted, this can be done in linear time. Every perfect binary search tree is a valid AVL tree. Viola :D

  • $\begingroup$ As you say, creating the sorted lists will take linear time, and we want to make an algorithm which is strictly faster. $\endgroup$ – Álvaro G. Tenorio Sep 2 '18 at 10:27
  • $\begingroup$ It is in linear time. How do expect it to be faster than that? $\endgroup$ – Vk1 Sep 3 '18 at 7:22
  • $\begingroup$ As you can see here, cs.stackexchange.com/questions/80436/avl-tree-partition it can be done in $\mathcal{O}(\log^2)$ $\endgroup$ – Álvaro G. Tenorio Oct 21 '18 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.