I'm having a trouble with understanding how to implement and find the median of a threaded binary search tree in constant time.
The tree consists of a worker's id and name.
The given details are given:
In a binary search tree with n nodes, There are n+1 left and right pointers with the value NIL. For every node z in the tree we make the following change: If left[z]=NIL then left[z] obtains the value of tree-predecessor(z); And if right[z]=NIL then right[z] obtains the value of tree-successor(z).
Basically, from what I understand it's a doubly threaded binary search tree.
I am not sure how to return the median in a constant time.
What I know is that if we want to return the median in O(n) in a regular binary search tree, then it is obtained using Morris in-order traversal and then easily calculated if the number of nodes is even or odd.
However, how can it be calculated in constant time?
I already done the traversal with in-order,post-order,pre-order using a linear time with the number of elements in it.
Please help me, stuck on it for quite a while.
thank you very much