PROVIDED CODE:

import java.util.*; import java.io.*;

// This class represents a tree of integers. public class IntTree { private IntTreeNode overallRoot;

public void limitLeaves(int n) { // TODO: Your code here }

////////////////////////////////////////////// // You can ignore code below // //////////////////////////////////////////////

// Constructs a tree with default numbers. public IntTree() { overallRoot = null; }

public IntTree(String s) { overallRoot = fromString(new StringBuilder(s.toLowerCase().trim())); }

public IntTreeNode getRoot() { return overallRoot; }

public void setRoot(IntTreeNode root) { overallRoot = root; }

// post: Prints the numbers in this tree in a pre-order fashion. public void print() { print(overallRoot); }

private void print(IntTreeNode root) { if (root != null) { System.out.print(root.data + " "); print(root.left); print(root.right); } }

public boolean equals(Object o) { if (o instanceof IntTree) { IntTree other = (IntTree) o; return toString().equals(other.toString()); } else { return false; } }

// post: Returns a text representation of the tree. public String toString() { return toString(overallRoot); }

private String toString(IntTreeNode root) { if (root == null) { return "null"; } else if (root.left == null && root.right == null) { return "[" + root.data + "]"; } else { return "[" + root.data + " " + toString(root.left) + " " + toString(root.right) + "]"; } }

private IntTreeNode fromString(StringBuilder s) { String next = nextToken(s); if (next.length() == 0 || next.equals("null") || next.equals("/")) { return null; } else { next = next.substring(1, next.length() - 1).trim(); // remove [] from ends StringBuilder nextBuilder = new StringBuilder(next); String rootStr = nextToken(nextBuilder); int data = Integer.parseInt(rootStr); String leftStr = nextToken(nextBuilder); String rightStr = nextToken(nextBuilder); return new IntTreeNode(data, fromString(new StringBuilder(leftStr)), fromString(new StringBuilder(rightStr))); } }

// Returns string representation of next complete node or data value from given buffer. private String nextToken(StringBuilder s) { while (s.indexOf(" ") == 0) { s.deleteCharAt(0); } if (s.length() == 0) { return ""; }

int i = 0; if (s.charAt(0) == '[' || s.charAt(0) == '(') { int depth = 0; do { if (s.charAt(i) == '[' || s.charAt(i) == '(') { depth++; } else if (s.charAt(i) == ']' || s.charAt(i) == ')') { depth--; } i++; } while (i 0); if (depth > 0) { throw new IllegalArgumentException("missing closing bracket in " + s); } } else { while (i

String result = s.substring(0, i).trim(); s.delete(0, i); while (s.indexOf(" ") == 0) { s.deleteCharAt(0); } return result; } }

_____________

// Class that represents a single node in the tree. public class IntTreeNode { public int data; public IntTreeNode left; public IntTreeNode right;

// Constructs a leaf node with the given data. public IntTreeNode(int data) { this(data, null, null); }

// Constructs a leaf or branch node with the given data and links. public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) { this.data = data; this.left = left; this.right = right; } }

The program should be written in Java, using only the provided methods. You may not import additional packages.

Additional INFO: no string was provided. added IntTreeNode class

5. Binary Trees Write a method called limitLeaves that takes an integer n as a parameter and that removes nodes from a tree to guarantee that all leaf nodes store values that are greater than n. For example, suppose a variable t stores a reference to the following tree: +----+ | 13 | +----+ 1 +--- -+ +--- - + | 18 | | 10 | +----+ +----+ / / . +----+ +----+ +----+ | 82 | | 17 | | 23 | +----+ +----+ +----+ 7 . +----+ +----+ +----+ +----+ | 12 | | 20 | | 92 | +----+ 1 8 | +----+ +----+ +----+ And we make the following call: t.limitLeaves (20); Then your method must guarantee that all leaf node values are greater than 20. So it must remove the leaves that store 8, 12, and 20. But notice that this creates a new leaf that stores 17 when its child is removed. This new leaf must also be removed. Thus, we end up with this tree: +- + | 13 | +-- + . + + +----+ | 18 | | 10 | +----+ +-- + 1 +-- + + | 821 | 23 | +----+ +----+ / +--- + | 92 | +----+ Notice that the nodes storing 13, 18, and 10 remain even though those values are not greater than 20 because they are branch nodes. Also notice that you might be required to remove nodes at many levels. For example, if the node storing 23 instead had stored the value 14, then we would have removed it as well, which would have led us to remove the node storing 10. Your method should remove the minimum number of nodes that satisfies the constraint that all leaf nodes store values greater than the given n. You are writing a method that will become part of the IntTree class. You may define private helper methods to solve this problem, but otherwise you may not assume that any particular methods are available. You are not allowed to change the data fields of the existing nodes in the tree, and you are not allowed to construct new nodes or additional data structures