So I am trying to implement split method in AVL tree(given a node with key X split the tree..) and since I have size field only for the AVL tree class,I can't find a way to find the size of each sub-tree after the split. I was thinking about adding each node a size field but this solution is too complicated for now because I will have to edit many of the code that I have written. I will be glad for solution(if exists, under those conditions) to know how to find the size of each sub-tree after the split(without time complexity above O(logn)).thank you!
It is not possible to determine the size of each side of the split in sub-linear time without attaching additional data to the node.