Suppose that the TreeNode class defined in BST contains a reference to the node?s parent, as shown in Programming Exercise 25.15. Implement the AVLTree class to support this change. Write a test program that adds numbers 1, 2, . . . , 100 to the tree and displays the paths for all leaf nodes.

Redefine?TreeNodeby adding a reference to a node?s parent, as shown below:

Reimplement the?insertand?deletemethods in the?BSTclass to update the parent for each node in the tree. Add the following new method in?BST:

/** Returns the node for the specified element.

* Returns null if the element is not in the tree. */

private TreeNode getNode (E element)

/** Returns true if the node for the element is a leaf */

private boolean isleaf (E element)

/** Returns the path of elements from the specified element

* to the root in an array list. */

public ArrayList getPath (E e)

Write a test program that prompts the user to enter 10 integers, adds them to the tree, deletes the first integer from the tree, and displays the paths for all leaf nodes. Here is a sample run:

BST.TreeNode #element: E #left: TreeNode #right: TreeNode #parent: TreeNode Enter 10 integers: 45 54 67 56 50 45 23 59 23 67 JEnter [50, 54, 23] [59, 56, 67, 54, 23]