Sample Input: + ( * ( 7 ( null null ) 3 ( null null ) ) 5 ( null null ) )

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

/** A binary tree in which each node has two children. */ public class BinaryTree { private Node root;

/** Constructs an empty tree. */ public BinaryTree() { root = null; }

/** Constructs a tree with one node and no children. @param rootData the data for the root */ public BinaryTree(Comparable rootData) { root = new Node(); root.data = rootData; root.left = null; root.right = 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; } }

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

import java.util.*;

public class PoD

{

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

/**

* Creates a mathematical equation based on the contents of a strict binary tree:

* - If the tree is empty, outputs: "0"

* - If the left tree ( and therefore right as well) is empty, returns tree data.

* - Otherwise: Outputs a mathematical expression of the form:

*

* "( leftEquation mathSymbol rightEquation )"

*

* where leftEquation and rightEquation are mathematical equations themselves

* based on the leftSubtree and rightSubtree, respectively.

*

*

* mathSymbol

* / \

* / \

* leftSubtree rightSubtree

*

*

* @param tree strict BinaryTree of interest

* @return String of mathematicial equation

*/

public static String equationMaker(BinaryTree tree)

{

/*

If the tree is empty, output: 0

Otherwise:

Output a mathemematical expression of the form: ( leftSide math rightSide )

where leftSide and rightSide can themselves

be mathematical equations.

(math)

/ \

/ \

leftSide rightSide

e.g. the following tree

*

/ \

/ \

+ -

/ \ / \

3 4 2 +

/ \

1 3

becomes

( ( 3 + 4 ) * ( 2 - ( 1 + 3 ) ) )

*/

String mathEquation;

return mathEquation;

}

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

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

BinaryTree newTree = buildTree(in);

String treeEquation = equationMaker(newTree);

System.out.println(treeEquation);

in.close();

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

}

/**

* Reads in data to form a binary tree:

* N ( L R )

* N = node data

* L = Left binary tree data (possibly of same form)

* R = Right binary tree data (possibly of same form)

* expects all nodes until reaching null

*

* e.g. input: a ( b ( null null ) c ( null null ) )

* creates tree:

* a

* / \

* b c

*/

public static BinaryTree buildTree(Scanner in)

{

String data = in.next();

BinaryTree left = null;

BinaryTree right = null;

//System.out.println(data);

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 equationMaker metho Input The main method (already completed) creates a strict binary tree and passes it to the method equationMaker Processing You are going to complete the details of the equationMaker method Details of the method and its expected parameters are described in the Javadoc comments preceding it. The method should . take in a binary tree . create a mathematical equation based on the contents of the tree o If the tree is empty, output: O o If the left tree ( and therefore right as well) is empty, return contents of tree Otherwise: Output a mathematical expression of the form: "(leftEquation mathSymbol rightEquation" where leftEquation and rightEquation are mathematical equations themselves based on the leftSubtree and rightSubtree, respectively nathSymbol LeftSubtree rightSubtree e.g. the following tree becomes 3 4)2 13)))" Output Output will be handled by the main method based on the value you return