Sample Input: m k ( c ( a ( null null ) e ( null null ) ) p ( null null ) )

=====================================================

/**

A binary tree in which each node has two children.

*/

public class BinaryTree

{

public Node root;

/**

Constructs an empty tree.

*/

public BinaryTree() { root = null; }

/**

Constructs a binary tree.

@param rootData the data for the root

@param left the left subtree

@param right the right subtree

*/

public BinaryTree(Comparable rootData, BinaryTree left, BinaryTree right)

{

root = new Node();

root.data = rootData;

root.left = null;

root.right = null;

if (left != null) { root.left = left.root; }

if (right != null){ root.right = right.root; }

}

class Node

{

public Comparable data;

public Node left;

public Node right;

}

/**

Checks whether this tree is empty.

@return true if this tree is empty

*/

public boolean isEmpty() { return root == null; }

/**

Gets the data at the root of this tree.

@return the root data

*/

public Comparable data() { return root.data; }

/**

Gets the left subtree of this tree.

@return the left child of the root

*/

public BinaryTree left()

{

BinaryTree result = new BinaryTree();

result.root = root.left;

return result;

}

/**

Gets the right subtree of this tree.

@return the right child of the root

*/

public BinaryTree right()

{

BinaryTree result = new BinaryTree();

result.root = root.right;

return result;

}

/**

Prints the contents of the tree in sorted order.

*/

public void print()

{

print(root);

System.out.println();

}

/**

Prints a node and all of its descendants in sorted order.

@param parent the root of the subtree to print

*/

private static void print(Node parent)

{

if (parent == null) { return; }

print(parent.left);

System.out.print(parent.data + " ");

print(parent.right);

}

}

===================================

import java.util.*;

public class PoD

{

//=============================================================================

/**

* Tries to add an object within the binary search tree

*

* @param obj Comparable to add to the tree

* @param tree BinaryTree of interest

* @return BinaryTree with new object added

*/

public static void addValue(Comparable value, BinaryTree tree)

{

}

//=============================================================================

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

Comparable value = in.next();

BinaryTree newTree = buildTree(in);

addValue(value, newTree);

newTree.print();

in.close();

System.out.print("END OF OUTPUT");

}

public static BinaryTree buildTree(Scanner in)

{

String data = in.next();

BinaryTree left = null;

BinaryTree right = null;

if (data.equals("null")) { return null;}

if (!in.next().equals("(")) { System.out.println("BAD INPUT: (L"); }

left = buildTree(in);

right = buildTree(in);

if (!in.next().equals(")")) { System.out.println("BAD INPUT: R)"); }

return new BinaryTree(data, left, right);

}

}

You are going to finish off PoD.java to finish the addValue method. Input The main method (already completed) creates a binary tree and passes a Comparable object (in this case a String) and binary tree to the method addValue Processing You are going to complete the details of addValue method. Details of each method and their expected parameters are described in the Javadoc comments preceding it. The method should take in a Comparable object decide where in the binary search tree the object fits add the object to the binary tree as a new node Output Output will be handled by the main method based on the results of your method. Note that the method returns void, but the output makes use of the changes that are made to the binary search tree as a result of the work done in your method