A sublinear time sub-quadratic work parallel algorithm for construction of an optimal binary search tree, in a special case of practical interest, namely where the frequencies of items to be stored are not too small, is given. A sublinear time sub-quadratic work parallel algorithm for construction of an approximately optimal binary search tree in the general case is also given. Sub-quadratic work and sublinear time are achieved using a fast parallel algorithm for the {\em column minima} problem for Monge matrices developed by Atallah and Kosaraju. The algorithms given in this paper take $O(n^{0.6})$ time with $n$ processors in the CREW PRAM model.A new version of the sequential subquadratic time algorithms for the same problems is also given. New parallel and sequential algorithms for height-limited binary search trees with very small height limitation are presented.