Part (a)
/** Creates two new nodes that each contain the same value as contained in t.
* These new nodes become the left and right child nodes of t.
* The original left child of t becomes the left child of the new left child,
* and the original right child of t becomes the right child of the new right child.
* @param t a reference to the node to be expanded
* Precondition: t is not null
*/
private static void expandNode(TreeNode t)
{
TreeNode left = new TreeNode(t.getValue(), t.getLeft(), null);
TreeNode right = new TreeNode(t.getValue(), null, t.getRight());
t.setLeft(left); ^{1}
t.setRight(right);
}
Notes:
 Not
t.getLeft() = left;
t.getRight() = right;
Part (b)
/** Grows the tree by expanding all nodes containing val in the subtree rooted at current
* @param current the root of the subtree to be processed
* @param val the value to be matched
*/
private static void growTreeHelper(TreeNode current, Object val)
{
if (current != null)
{
growTreeHelper(current.getLeft(), val);
growTreeHelper(current.getRight(),val);
if (current.getValue().equals(val))
expandNode(current);
}
}
Part (c)
Method  BigOh 
expandNode  O(1) 
growTreeHelper  O(n) 
