0
$\begingroup$

I need to find a way to split an AVL tree based on the amount of nodes in the tree, lets assume you get a number $k$ and if the number of nodes in the tree is multiplication of $k$ you need to find the maximum of each tree in the $k$ trees.

for example: for $k=3$

    3
   / \
  2   9        
 /   / \
1   4   11

after the split you get 3 trees (the function doesn't need to actually build those trees):

    2     3      9
   /       \      \
  1         4     11

you can also think about it like subgrouping the AVL tree to 3 sub groups {1,2},{3,4},{9,11}

the nodes should be grouped in increasing order (like printing in-order transverse and splitting it)

and the function should return 2,4,11

This problem should be solved in complexity of $log(n)$ while $n=$ the original number of nodes.

I wasn't able to think about a solution in the desired complexity, I thought about using in-order traversal but every solution is in $O(n)$.

$\endgroup$
8
  • $\begingroup$ Is it guaranteed that $n$ is divisible by $k$? $\endgroup$
    – Russel
    Feb 12 at 10:27
  • $\begingroup$ yes it is garneted $\endgroup$
    – 3xhaust
    Feb 12 at 10:29
  • $\begingroup$ Do you have additional requirement as to how to choose which nodes are to be grouped together? Why group (3,4) and (9,11) instead of (3,9) and (4,11)? Please edit the question to include this. $\endgroup$
    – Russel
    Feb 12 at 10:36
  • $\begingroup$ the nodes should be grouped in increasing order (like printing in-order transverse and splitting it) $\endgroup$
    – 3xhaust
    Feb 12 at 11:49
  • $\begingroup$ Does each node contain a counter of how many nodes are in that subtree? Or something similar? Because just going by the AVL invariant of height difference it seems difficult to avoid a full traversal to ensure you've got exactly the right split points. Either way, you can't do better than $O(k)$ since that's your output size, so when $k > \log n$ that is the limiting factor. $\endgroup$
    – orlp
    Feb 12 at 20:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.