CSC 143 7. What would happen if we removed the root != null test from the printP
ID: 3848267 • Letter: C
Question
CSC 143
7. What would happen if we removed the root != null test from the printPreorder method?
8. Write a method called printPostorder that could be added to the IntTree class and that prints a postorder traversal of the tree.
9. Write a method called printMirror that could be added to the IntTree class and that prints a backward inorder traversal of the tree. That is, for a given node, it examines the right subtree, then the node itself, then the left subtree.
10. Why do many recursive tree methods use a public/private pair? What is the difference between the header of the public method and that of the private method?
11. Write a method called size that could be added to the IntTree class and that returns the total number of nodes in the tree.
12. Write methods called min and max that could be added to the IntTree class and that return the smallest and largest values in the tree respectively. For example, if a variable called tree stores the values shown in Self-Check Problem 5, the call of tree.min() should return –2 and the call of tree.max() should return 94. If the tree is empty, the methods should throw an IllegalStateException.
Need these question done ASAP
Explanation / Answer
7. What would happen if we removed the root != null test from the printPreorder method?
We ae calling printPreorder on the node's child recursively.. if we wouldn't have checked it, then in case of leaf node or node with one child only, the root.data statement would have thrown an NullPointerException, because a child was null, for which printPreorder method was called.
8. Write a method called printPostorder that could be added to the IntTree class and that prints a postorder traversal of the tree.
// postOrder: prints the tree contents using a postorder traversal
public void printPostorder() {
System.out.print("postorder:");
printPostorder(overallRoot);
System.out.println();
}
// post: prints in postorder the tree with given root
private void printPostorder(IntTreeNode root) {
if (root != null) {
printPostorder(root.left);
printPostorder(root.right);
System.out.print(" " + root.data);
}
}
9. Write a method called printMirror that could be added to the IntTree class and that prints a backward inorder traversal of the tree. That is, for a given node, it examines the right subtree, then the node itself, then the left subtree.
// printMirror: prints the tree contents using a backward inorder traversal
public void printMirror() {
System.out.print("printMirror:");
printMirror(overallRoot);
System.out.println();
}
// printMirror: prints in backward inorder the tree with given root
private void printMirror(IntTreeNode root) {
if (root != null) {
printPostorder(root.right);
System.out.print(" " + root.data);
printPostorder(root.left);
}
}
10. Why do many recursive tree methods use a public/private pair? What is the difference between the header of the public method and that of the private method?
The private method consume a particular node to do the work, and it does the work for the subtree starting from that node only, while the public method is exepected to do the work for the whole tree, i.e. starting from the root of the tree.
11. Write a method called size that could be added to the IntTree class and that returns the total number of nodes in the tree.
// returns the size of overall tree
public int getSize() {
return getSize(overallRoot);
}
private int getSize(IntTreeNode root) {
if(root == null)
return 0;
return 1 + getSize(root.left) + getSize(root.right);
}
12. Write methods called min and max that could be added to the IntTree class and that return the smallest and largest values in the tree respectively. For example, if a variable called tree stores the values shown in Self-Check Problem 5, the call of tree.min() should return –2 and the call of tree.max() should return 94. If the tree is empty, the methods should throw an IllegalStateException.
// finds the lowest node in the tree
public int min() {
if(overallRoot== null)
throw new IllegalStateException();
return min(overallRoot);
}
private int min(IntTreeNode root) {
int value = root.data;
if(root.left != null) {
int leftMin = min(root.left);
if(leftMin < value) {
value = leftMin;
}
}
if(root.right != null) {
int rightMin = min(root.right);
if(rightMin < value) {
value = rightMin;
}
}
return value;
}
// finds the maximum node in the tree
public int max() {
if(overallRoot== null)
throw new IllegalStateException();
return max(overallRoot);
}
private int max(IntTreeNode root) {
int value = root.data;
if(root.left != null) {
int leftMax = min(root.left);
if(leftMax > value) {
value = leftMax;
}
}
if(root.right != null) {
int rightMax = min(root.right);
if(rightMax > value) {
value = rightMax;
}
}
return value;
}