JAVA: Complete the following method removeLeaves() RECURSIVELY USING ONE HELPER
ID: 3916633 • Letter: J
Question
JAVA: Complete the following method removeLeaves() RECURSIVELY USING ONE HELPER FUNCTION.
public class MyIntSET {
private Node root;
private static class Node {
public final int key;
public Node left, right;
public Node(int key) { this.key = key; }
}
// tree is semi-perfect if every node is semi-perfect
// A node with 0 children is semi-perfect.
// A node with 1 child is NOT semi-perfect.
// A node with 2 children is semi-perfect if (size-of-larger-sized-child <= size-of-smaller-sized-child * 3)
// Here, larger and smaller have to do with the SIZE of the children, not the key values.
// hint: in the helper, return -1 if the tree is not semi-perfect, otherwise return the size
public boolean isSemiBalanced() {
//
//
// 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() {
Explanation / Answer
public void removeLeaves() { root = removeLeavesUtil(root); } public Node removeLeavesUtil(Node start) { if(start == null) { return null; } if(start.left==null && start.right==null) { return null; } start.left = removeLeavesUtil(start.left); start.right = removeLeavesUtil(start.right); return start; }
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.