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?