Flatten a binary tree into a list:

Walking the labelled tree in pre-order and copying out the nodes sequentially, we get: (M,14), (J,9), (O,4), (K,2), (G,0), (P,1), (S,3), (B,8), (V,6), (E,5), (Q,7), (A,13), (T,11), (N,10), (F,12), (D,22), (U,16), (I,15), (H,18), (C,17), (W,20), (R,19), (L,21).

Write the routine in pseudo-code that reconstitutes any binary tree that has been flattened in this way. Remember, recursion is your friend! (Or stacks. The stack is your friend too.)

Your routine should be (n). Explain the big-Oh runtime of your routine.

Plattening an object means transforming (serializing) it somehow into a list. In Java, if there is a method to flatten an object, the class is called serializable. An object from a serializable class can be flattened into an array, and then written out to disk for saving. Later, another java program - or the same one- can read the sequence representing the flattened object off disk and reconstitute the object in memory. Therefore, any serializable class must also define how a flattened object is rebuilt into (a copy of) the original. Consider binary trees. How could we flatten a binary tree into a list? Easy! Just walk the tree (pre-order, in-order, or post-order) and write it out. Harder is how could we flatten a binary tree into a list in such a way that we could easily reconstitute it from the list. Here is the flattening half of one way to do this. 1. counter0 2. Walk the tree in-order. At each node, add an extra label with counter's value counter++ 3. Walk the tree pre-order and copy the nodes into a list sequentially, along with the new labels. For example, consider the following binary tree