Given n records stored alphabetically on a tape, any comparison search procedure can be characterized by a binary tree. The complete binary tree (binary search) uses the minimum number of comparisons but not the minimum number of movements. The linear binary tree (sequential search) uses the minimum number of movements but not the minimum number of comparisons. A tape-optimal tree is a tree which minimizes the total cost of comparisons and movements. The tape-optimal tree is a “hybrid” of the linear tree and the complete binary tree, and is characterized for arbitrary n.

A new algorithm for constructing minimum cost binary trees in $O(n \log n)$ time is presented. The algorithm is similar to the well-known Hu-Tucker algorithm. Our proof of validity is based on finite variational methods and is therefore quite different and somewhat simpler than the proof for the Hu-Tucker algorithm. Our proof also yields some additional information about the structure of minimum cost binary trees. This permits a linear time implementation of our algorithm in a special case.