1

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.

Eduard Rostomyan
  • 7,050
  • 2
  • 37
  • 76
  • 2
    If you can modify the tree to a rank-tree (each node also holds the number of nodes in the subtree it's a root of), it can be done in O(logn) time and space, without changing the insertion/deletion/search of the tree. – amit Mar 10 '15 at 12:05

3 Answers3

6

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.

amit
  • 175,853
  • 27
  • 231
  • 333
  • Can't it be done with `O(1)` extra memory for rank trees? We only care about the current node in that solution. – IVlad Mar 10 '15 at 12:10
  • @IVlad Think you are right, I was thinking recursively, but there is no problem on doing it iteratively with keeping only current. – amit Mar 10 '15 at 12:12
1

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.

JuniorCompressor
  • 19,631
  • 4
  • 30
  • 57
1

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.

Community
  • 1
  • 1
IVlad
  • 43,099
  • 13
  • 111
  • 179