A related problem to the OBST problem is when there is no order between the keys and there are probabilities associated only with the gaps and the objective is to build a binary tree with minimum expected weighted path length from the root. This is called the Huffman Tree Problem