Encoding a Binary Search Tree in Constant Time on BSR

Constant time solutions on BSR can be found in the literature to many applications, such as parenthesis matching, tree decoding, tree reconstruction, and etc. However, the problem of encoding a tree in constant time on BSR is still open. In this paper, some properties will be discussed on binary search trees and the i-p sequence, and based on the properties, a constant time algorithm on BSR is proposed for encoding a binary search tree into its i-p sequence, which is the first constant time solution to the problem on any model of computation.