Assignment II

Due date Feb.13.

For the following problems, use the programming language of your choice to define data structures and algorithms. Java, C, C++, Ada, or Pascal are all fine. Perl or Virtual Basic are not.

1. Tree Isomorphism (from text, C-2.12). Intuitively, two trees are isomorphic if they have the same shape (the values stored at corresponding nodes can be different). Write an algorithm to test whether two trees are isomorphic, and estimate its worst-case running time.

2. Assume you have a binary tree with the following operations defined on tree nodes: LeftChild, RightChild, Parent, Is_Leaf, and Is_Root. Implement the operation NextInOrder, which yield the node that follows a given node in an in-order traversal. Needless to say, the tree is not threaded!

Similarly, Implement the operation NextPreorder.

3. We have some binary tree T (not necessarily proper, i.e. some internal nodes may have a single descendant), with values stored at internal and external nodes. Suppose you are given the listing of the values stored at the nodes, obtained by an inorder traversal of the tree. Clearly, from this list it is not possible to rebuild the tree, because all you know for sure is the value stored at the root. Many trees can have the same preorder traversal (show this by building two trees whose preorder listing is a b c d e).
Show that if you are given the inorder listing of the values as well, it is possible to rebuild the tree. Write an algorithm to achieve this. Assume that your node class includes operation SetLeftChild, SetRightChild, and SetValue. Inputs are two sequences (arrays): PreSeq and InSeq.

4. From text: C-2.21. Write an algorithm to find the lowest common ancestor of two nodes in a tree, that is to say the root of the smallest subtree in which both nodes appear. What is the complexity of your algorithm?