0

I want to find the median of an AVL tree.

Here is what I think I should do:

Since we know that the BF of the root is in {-1,0,1}, than:

If the BF=0: return root

If the BF=-1: return root.right

If the BF=1: return root.left

Am I right here?

I know we can hold augmented data of the size of each sub tree, and the number of nodes in all of the tree, and then calculate the median in O(1) as well, but I want a simple and different method.

Thanks a lot!

CalculusLover
  • 127
  • 5
  • 1
    If two trees have the same height, they do not necessarily have the same number of elements. – Henry Jul 05 '21 at 12:03
  • For the uninitiated, could you please explain what is a BF? – Stef Jul 05 '21 at 12:06
  • See also these three questions with the same title: https://stackoverflow.com/questions/14823157/get-median-from-avl-tree https://stackoverflow.com/questions/28528533/find-median-of-avl-tree https://stackoverflow.com/questions/31639080/finding-median-in-avl-tree – Stef Jul 05 '21 at 12:07
  • 1
    @Stef balance factor, but as Henry observes, it's controlling the heights of the subtrees, not the sizes (and also the predecessor/successor of root in the tree are in general not root.left/root.right). – David Eisenstat Jul 05 '21 at 12:22
  • 2
    No, it is not possible to do this in O(1). The median can be at any depth in the tree, so at least you have to walk towards that node, which takes O(logn). – trincot Jul 05 '21 at 13:47
  • @500-InternalServerError, this is not necessarily true. See first comment above. – trincot Jul 05 '21 at 14:32
  • 1
    An AVL tree of height 3, can have a balanced root, with at the left side a perfect tree of 7 nodes, and at the right side a tree with just 4 nodes. So necessarily the median is not the root, but is somewhere in the left subtree. – trincot Jul 05 '21 at 14:44
  • @trincot: oh, right, I get it now. – 500 - Internal Server Error Jul 05 '21 at 14:45

0 Answers0