CODEWITHSUNDEEP
c++algorithmvectortime-complexitybinary-search-tree
Eduard Rostomyan
Eduard Rostomyan

Reputation: 6546

Find the median of binary search tree, C++

Once I was interviewed by "One well known company" and the interviewer asked me to find the median of BST. 

int median(treeNode* root)
{

}

I started to implement the first brute-force solution that I came up with. I fill all the data into a std::vector<int> with inorder traversal (to get everything sorted in the vector) and got the middle element. So my algo is O(N) for inserting every element in the vector and query of middle element with O(1), + O(N) of memory. So is there more effective way (in terms of memory or in terms of complexity) to do the same thing.
Thanks in advance.

Upvotes: 1

Views: 3975

Answers (3)

JuniorCompressor
JuniorCompressor

Reputation: 20015

The binary tree offers a sorted view for your data but in order to take advantage of it, you need to know how many elements are in each subtree. So without this knowledge your algorithm is fast enough.

If you know the size of each subtree, you select each time to visit the left or the right subtree, and this gives an O(log n) algorithm if the binary tree is balanced.

Upvotes: 1

amit
amit

Reputation: 178431

It can be done in O(n) time and O(logN) space by doing an in-order traversal and stopping when you reach the n/2th node, just carry a counter that tells you how many nodes have been already traversed - no need to actually populate any vector.

If you can modify your tree to ranks-tree (each node also has information about the number of nodes in the subtree it's a root of) - you can easily solve it in O(logN) time, by simply moving torward the direction of n/2 elements.

Upvotes: 6

IVlad
IVlad

Reputation: 43477

Since you know that the median is the middle element of a sorted list of elements, you can just take the middle element of your inorder traversal and stop there, without storing the values in a vector. You might need two traversals if you don't know the number of nodes, but it will make the solution use less memory (O(h) where h is the height of your tree; h = O(log n) for balanced search trees).

If you can augment the tree, you can use the solution I gave here to get an O(log n) algorithm.

Upvotes: 1

Related Questions