JAVA: Complete the following methods below(3) RECURSIVELY USING ONE HELPER FUNCT
ID: 3916914 • Letter: J
Question
JAVA: Complete the following methods below(3) 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() {
//TODO
//
// 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
//
// the number of nodes in the tree, "above" depth k (not including k)
// include node n if depth(n) < k
public int sizeAboveDepth(int k) {
//TODO
Explanation / Answer
public boolean isSemiBalanced() { return isSemiBalancedUtil(root); } private boolean isSemiBalancedUtil(Node start) { if(start == null) { return true; } if(start.left==null && start.right==null) { return true; } else if(start.left==null || start.right == null) { return false; } else { // with 2 childs int sizeLeft = sizeUtil(root.left); int sizeRight = sizeUtil(root.right); if(sizeLeft > sizeRight) { if(sizeLeft = sizeRight) { return isSemiBalancedUtil(start.left) && isSemiBalancedUtil(start.right); } else { return false; } } } } ==================================================== public void addZeroToSingles() { addZeroToSinglesUtil(root); } private void addZeroToSinglesUtil(Node start) { if(start == null) { return; } if(start.left != null && start.right != null) { addZeroToSinglesUtil(start.left); addZeroToSinglesUtil(start.right); return; } if(start.left == null && start.right == null) { return; } if(start.left == null) { start.left = new Node(0); } else { start.right = new Node(0); } } ==================================================== public int sizeAboveDepth(int k) { return sizeAboveDepthUtil(root, 0, k); } private int sizeAboveDepthUtil(Node start, int current, int depth) { if(current >= depth) { return 0; } if(start == null) { return 0; } return 1 + sizeAboveDepthUtil(start.left, current + 1, depth) + sizeAboveDepthUtil(start.right, current + 1, depth); }Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.