# how can i return the median of a threaded binary search tree in constant time?

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.

thank you very much

• The only way to get constant (not even logarithmic) time it to not traverse the tree at all. Is it some quiz or real world problem. – max630 Jul 25 '18 at 5:48
• i am sorry but i don't understand. could you please elaborate? – BeginningMath Jul 25 '18 at 6:00
• I cannot prove it now, and not in the comment space, but if you would traverse the tree with N elements before finding the answer, then you are very likely to spend at non-constant number of steps, maybe as low as `log N` but still non-constant – max630 Jul 25 '18 at 6:19
• @BeginningMath: For a constant-time algorithm, you would need to visit the same number of nodes for a tree of 1.000 nodes and a tree of 1.000.000 nodes. The algorithm can not depend on the number of nodes in the tree. – Bart van Ingen Schenau Jul 25 '18 at 7:22

If by 'threaded binary search tree' you mean 'balanced binary tree'.

Easy. Return the root!

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

The key feature of a balanced binary tree is that you are balancing nodes on the left and right as you modify the tree, keeping half of them on the left, and half on the right ;-) The median then is always at the root of the tree. So trick question ;-)

If you mean something else - you likely cannot find it in constant time. If you have to wander through the tree to almost any degree hunting around, that will almost have to depend on how big the tree is, and so not be constant.

• thank you very much for your comment. my question was about a binary search tree becoming a threaded binary search tree, and i'm sorry if i'm not sure how to implement the concept of a balanced binary tree here. basically, i need to store worker's name and his id in the tree and then return the media in constant time – BeginningMath Jul 26 '18 at 9:18
• Unfortunately a “balanced” tree doesn't always mean that there are the same number of nodes on the left and right, but usually means that all sub-trees have the approximately same height. Given a height-balanced binary tree, there may still be height^2 more nodes on one side. AFAIK maintaining a size-balanced tree is difficult to maintain under insertions (unless we relax the problem to require only the root node to be size-balanced). – amon Jul 26 '18 at 9:35

For a size-balanced binary search tree of odd size, the root node represents the median.

For a size-balanced binary search tree of even size, the approach depends on your definition of the median. In case you simply average the two central values, you would have average the root value with its neighboring value on the larger subtree's side. In a linked tree finding that neighbor is a constant-time operation.

The difficult part here is keeping the tree size-balanced (weight-balanced). Most tree balancing algorithms balance the height instead, which is uninteresting here. Weight-balancing algorithms typically keep the left and right weights within some factor of each other, but here we want the weight difference to be zero or one.

AFAIK this is easy to do given O(n) insertions (e.g. by rebuilding the tree after each insertion).

• could you provide a code snippet so i could understand it better please? – BeginningMath Jul 27 '18 at 12:10

for sake of simplicity, we'll assume that the median is the value at the ceil(n/2) index of the inorder traversal(1-indexed). at the head of the tree add a pointer to the median node & count of the number of nodes (n). maintenance: on every node insertion/deletion hold the old n in a temp variable, increment n by one and then check if the median, ( ceil(n/2)), index value has changed. if it grew by 1 set the median's successor as the median if it got smaller by 1 set the median's predecessor as the median This way you can simply return the median in constant time.

• So basically you're saying "Maintain a stored median as you add or remove nodes. Then, retrieve the stored median in O(1)?" – Robert Harvey Jul 25 '18 at 15:23
• Basically yes:) – Efi Shtainer Jul 25 '18 at 22:07
• but if i store the median and then retrieve it, wouldn't the total cost be maintaining median and storing media + returning it > constant time? – BeginningMath Jul 27 '18 at 14:07
• The cost of returning it will be constant time and maintenance is O(n) in a non-balanced tree and O(lgn) in a balanced one, but since insertion & removal are 0(n)/0(lgn) accordingly anyway, it doesn't affect the complexity, hence 0(1) = constant. – Efi Shtainer Jul 29 '18 at 11:30