Consider the reversal of the problem from the previous exercise. Now you are the recipient of such a message, containing a textural representation of a binary search tree as described in the previous exercise. Describe an algorithm running in O(n log n) time, or better, for reconstructing the binary search tree, T, that is represented in this message.

Data From Previous Exercise.

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

Transcribed Image Text:

10 20 30 40