Find the median of an AVL tree in o(log(n)) time using the given information?

Question

Given you know the minimum and maximum value of the AVL tree and that the tree only contains distinct integers, find the median of the tree?

Answer 1

k,tree,direction,currentPosition params to the recursive function (the antecedent frame will take f(k,tree,null,null) as its arguments to solve the problem. The implementation frame will receive this initially as null,null for direction and position, and if it is the implementation frame, the current position will be adjusted accordingly. If it is not an implementation frame, then we got here by some means, and our current position and direction would have changed, so now our current position at this frame will be adjusted based on the another piece of logic provided as well.

//implementation by Anthony Toorie
f(k,tree,direction,currentPosition){ 
//   let currentPosition = currentPosition
   if(!direction && !currentPosition){
      currentPosition = tree.left
   }

   if(direction === "left"){
      currentPosition = currentPosition - |tree.right|
   }

   if(direction === "right"){
      currentPosition = currentPosition - |tree.left|
   }

   if(currentPosition === k){
      return tree.value
   }

   if(currentPosition < k){
      return f(k,tree.left,"left",currentPosition)
   }

   if(currentPosition > k){
      return f(k,tree.right,"right",currentPosition)
   }
}

Sources :

https://en.wikipedia.org/wiki/Order_statistic_tree

|X| denotes the number of nodes for that tree X or subtree X.

Heavily based off quickselect aglorithm.

This will only be able to give you O(logN) in the worst case given some input N iff the tree is height-conservative or balanced. In the worst case, for a regular aka non balanced BST, the runtime would be O(N). And furthermore, on a regular tree, you would have in the worst case O(N) but also in the best case O(1) and average case O(N) as well. A tree should only contain distinct numbers, and the elements in the tree should be sortable.