Fill in the code for all 5 functions so they do what is specified. Remember that
ID: 3870532 • Letter: F
Question
Fill in the code for all 5 functions so they do what is specified. Remember that every function must be recursive with a helped function, and that the Node class and first line may not be altered in any way.
Restrictions:
* - DO NOT change the Node class.
* - DO NOT change the first line of any function: name, parameters, types.
* - you may add new functions, but don't delete anything
* - functions must be recursive
* - no loops
* - each function must have exactly one recursive helper function, which you add
* - each function must be independent --- do not call any function other than the helper
* - no fields (variables declared outside of a function)
NODE CLASS:
private static class Node {
public final int key;
public Node left, right;
public Node(int key) { this.key = key; }
}
* Mutator functions
* HINT: all of these are easier to write if the helper function returns Node, rather than void.
*/
#1
// remove all subtrees with odd roots (if node is odd, remove it and its descendants)
// A node is odd if it has an odd key
// If the root is odd, then you should end up with the empty tree
public void removeOddSubtrees () {
// TODO
}
#2
// remove all subtrees below depth k from the original tree
public void removeBelowDepth(int k) {
// TODO
}
#3
// add a child with key=0 to all nodes that have only one child
// (you do not need to retain symmetric order or uniqueness of keys, obviously)
public void addZeroToSingles() {
// TODO
}
#4
// remove all leaves from the original tree
// if you start with "41", then the result is the empty tree.
// if you start with "41 21 61", then the result is the tree "41"
// if you start with the BST "41 21 11 1", then the result is the tree "41 21 11"
// if you start with the BST "41 21 61 11", then the result is the tree "41 21"
// Hint: This requires that you check for "leafiness" before the recursive calls
public void removeLeaves() {
// TODO
}
#5
// remove all nodes that have only one child by "promoting" that child
// repeat this recursively as you go up, so the final result should have no nodes with only one child
// if you start with "41", the tree is unchanged.
// if you start with "41 21 61", the tree is unchanged.
// if you start with the BST "41 21 11 1", then the result is the tree "1"
// if you start with the BST "41 21 61 11", then the result is the tree "41 11 61"
// Hint: This requires that you check for "singleness" after the recursive calls
public void removeSingles() {
// TODO
}
Explanation / Answer
#1
public void removeOddSubtrees () {
if(left.key%2 !=0) left=null;
if(right.key%2 !=0) right=null;
if(left!=null) left.removeOddSubtrees();
if(right!=null) right.removeOddSubtrees();
}
#2
public void removeBelowDepth(int k) {
if(k==0)removeNode();
else{
left.removeBelowDepth(k-1);
right.removeBelowDepth(k-1);
}
}
#3
public void addZeroToSingles() {
if (left=null){
Node n = new Node(0);
left=n;
}
else if (right=null){
Node n = new Node(0);
right=n;
}
else{
left.addZeroToSingles();
right.addZeroToSingles();
}
}
#4
public void removeLeaves() {
if(left==null && right==null) remove(this);
else{
left.removeLeaves();
right.removeLeaves();
}
}
#5
public void removeSingles() {
if(left==null && right!=null)right.removeNode();
if(right==null && left!=null)left.removeNode();
left.removeSingles();
right.removeSingles();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.