30

In Problem 2, it was observed that in any binary tree T whose pre-order traversal yields the sequence 1, 2, ..., n, (i.e., pre-order(T)={1, 2, ..., n]), the root of every subtree T' of T has the minimum label in T' (ie., min(T')=root(T')). In this problem, you will prove this observation by induction, but to make such a proof easier, we will generalize the problem a little bit as described next. Generalization: Assume the labels of the nodes of T are arbitrary distinct numerical values (i.e., not necessarily the successive integers 1 through n), and assume that the pre-order traversal of T lists (ie., prints) the node labels in a sorted order (i.e., pre-order(T)=a sorted sequence). Let's call such trees canonically labeled trees. Prove by induction that for every subtree T' of a canonically labeled tree T, min(T')=root(T'). Hint: the induction is on the number of nodes of T