It is sometimes necessary to send a description of a binary search tree in text form, such

Question:

It is sometimes necessary to send a description of a binary search tree in text form, such as in an email or text message. Since it is a significant challenge to draw a binary search tree using text symbols, it is useful to have a completely textural way of representing a binary search tree. Fortunately, the structure of a binary search tree is uniquely determined by labeling each node with its preorder and postorder numbers. Thus, we can build a textural representation of a binary search tree T by listing its nodes sorted according to their preorder labels, and listing each node in terms of its contents and its postorder label. For example, the tree of Figure 3.10 would be represented as the string,

[(10, 9),(∅, 1),(20, 8),(∅, 2),(30, 7),(∅, 3),(40, 6),(∅, 5),(∅, 6)].

Describe an O(n) time method for converting an n-node binary search tree, T, into such a textural representation.

Figure 3.10