Write a recursive body for the following static method that copies and returns a
ID: 3858864 • Letter: W
Question
Write a recursive body for the following static method that copies and returns a given BinaryTree<Integer>. Note that the given BinaryTree must be restored, i.e., its outgoing value must be the same as its incoming value. [JAVA]
/**
* Returns a copy of the the given {@code BinaryTree}.
*
* @param t
* the {@code BinaryTree} to copy
* @return a copy of the given {@code BinaryTree}
* @ensures copy = t
*/
public static BinaryTree<Integer> copy(BinaryTree<Integer> t) {...}
Explanation / Answer
public class BinaryTree {
public int value;
public BinaryTree left;
public BinaryTree right;
public BinaryTree(int value, BinaryTree left, BinaryTree right)
{
this.value = value;
this.left = left;
this.right = right;
}
public static BinaryTree generate(BinaryTree root) {
// allocate a counter and delegate to the recursive method
int[] counter = {1};
return generate(root, counter);
}
/**
* Recursive method to generate a copy of a binary tree
* with values indicating the preorder traversal order.
*
* @param root
* the root of the tree to copy
* @param counter
* an array containing the traversal order counter as its
* first element. On entry, it should contain the value to
* use for the root of the generated (sub)tree. On return,
* it will contain one more than the last value used.
*/
private static BinaryTree generate(BinaryTree root, int[] counter) {
// recursion base case
if (root == null) {
return null;
}
// capture current value and increment the counter
int value = counter[0];
++counter[0];
// generate left subtree - this will change the counter unless
// the left subtree is null
BinaryTree left = generate(root.left, counter);
// generate right subtree - may change the counter
BinaryTree right = generate(root.right, counter);
// Complete the copy by generating the root node;
// return the result
return new BinaryTree(value, left, right);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.