Homework # 3 BinaryNode solution

Write the 5 methods that are next to your name. All methods must be added to
the BinaryNode class. Feel free to use the methods in that class and
to write your own private helper methods. Follow the same rules for submitting
the homeworks as in Hw#1 and Hw#2.



Method 1. Add the method prePlusIn to the BinaryNode class.

The method has the header

public static <T BinaryNode<T prePlusIn( T[] pre, T[] in)

and takes as input the preorder and the inorder traversals of a the items
of a binary tree and constructs a tree with these traversals. It returns
the root of the tree. Assume that none of the two traversals has duplicate
items. The method throws an IllegalArgumentException if it is not possible
to construct the tree.

Method 2. Add the method postPlusIn to the BinaryNode class.

The method has the header

public static <T BinaryNode<T postPlusIn( T[] post, T[] in)

and takes as input the postorder and the inorder traversals of a binary tree.
and constructs a tree that with these traversals. It returns the root
of the tree. Assume that none of the two traversals has duplicate
items. The method throws an IllegalArgumentException if it is not possible
to construct the tree.

Method 3. Add the method

public static <T BinaryNode<T levelsPlusIn(T[] in, T[] levels)

that takes as input the inorder traversal and the traversal by levels of
a binary tree and constructs the tree. It returns the root of the tree. Assume that
none of the two traversal have duplicate items.
Throw an IllegalArgumentException if this cannot be done.

Method 4. Add the method

public void iterativePostOrder()

that prints the nodes of the tree with root this in postorder,
without using recursion. Use a stack.

Method 5. Add the method

public void printByLevels()

That prints the nodes of the tree by levels. Use a queue.

Method 6. Add the method

public void iterativeInOrder()

that prints the nodes of the tree with root this in inorder,
without using recursion. Use a stack.

Maethod 7. Add the method

public BinaryNode<T parent(BinaryNode<T n)

that finds the parent of the node n in this tree.
If n = null throw an IllegalArgumentException.
If n = this or n does not occur in the tree return null.

Method 8. Two trees are equal if they have the same address set and
the values at the same address are equal.
Write the method

public boolean equals(BinaryNode<T r)

that returns true if the tree r is equal
to this and false otherwise. Some of the items may be null. Use equals
to check for equality.

Method 9. Two trees are isomorphic if one of them can be derived from the other
by swapping some of the left and right children.
Write the method

public boolean isomorphic(BinaryNode<T r)

that returns true if the tree r is isomorphic to this and false otherwise.
Some of the items may be null. Use the equals method to check for equality.


Method 10. Write the method

public static <T ArrayList<T longestPath(BinaryNode<T root)

that returns a longest path in the tree root. The first item of
the array list is the value of the root.