I need help with a Java problem please, I will give a good rating! Complete the
ID: 3887718 • Letter: I
Question
I need help with a Java problem please, I will give a good rating!
Complete the accessor functions in MyIntSET.java:
I have the size() function finished but not sure how to code the rest... Here is the copy/pasted java file:
MyIntSET.java:
import stdlib.*;
/* ***********************************************************************
* A simple BST with int keys
*
* Recall that:
* Depth of root==0.
* Height of leaf==0.
* Size of empty tree==0.
* Height of empty tree=-1.
*
* TODO: complete the functions in this file.
*
* 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, except printLeftI
* - no loops, except in printLeftI (you cannot use "while" "for" etc...)
* - 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)
*************************************************************************/
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; }
}
public void printLeftI () {
Node x = root;
while (x != null) {
StdOut.println(x.key);
x = x.left;
}
}
// the number of nodes in the tree
public int size() {
return size (root, 0);
}
private static int size (Node x, int sz) {
if (x != null) {
sz = sz + 1;
sz = size (x.left, sz);
sz = size (x.right, sz);
}
return sz;
return 0;
}
// Recall the definitions of height and depth.
// in the BST with level order traversal "41 21 61 11 31",
// node 41 has depth 0, height 2
// node 21 has depth 1, height 1
// node 61 has depth 1, height 0
// node 11 has depth 2, height 0
// node 31 has depth 2, height 0
// height of the whole tree is the height of the root
// the height of the tree
public int height() {
// TODO
return 0;
}
// the number of nodes with odd keys
public int sizeOdd() {
// TODO
return 0;
}
// The next three functions compute the size of the tree at depth k.
// It should be the case that for any given k,
//
// sizeAbove(k) + sizeAt(k) + sizeBelow(k) = size()
//
// The words "above" and "below" assume that the root is at the "top".
//
// Suppose we have with size N and height H (so max depth also H).
// For such a tree, we expect
//
// sizeAboveDepth (-1) = 0
// sizeAtDepth (-1) = 0
// sizeBelowDepth (-1) = N
//
// sizeAboveDepth (0) = 0
// sizeAtDepth (0) = 1
// sizeBelowDepth (0) = N-1
//
// sizeAboveDepth (H+1) = N
// sizeAtDepth (H+1) = 0
// sizeBelowDepth (H+1) = 0
//
// the number of nodes in the tree, at exactly depth k
// include node n if depth(n) == k
public int sizeAtDepth(int k) {
// TODO
return 0;
}
// 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
return 0;
}
// the number of nodes in the tree, "below" depth k (not including k)
// include node n if depth(n) > k
public int sizeBelowDepth(int k) {
// TODO
return 0;
}
// tree is perfect if for every node, size of left == size of right
// hint: in the helper, return -1 if the tree is not perfect, otherwise return the size
public boolean isPerfectlyBalancedS() {
// TODO
return false;
}
// tree is perfect if for every node, height of left == height of right
// hint: in the helper, return -2 if the tree is not perfect, otherwise return the height
public boolean isPerfectlyBalancedH() {
// TODO
return false;
}
// tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right
// A node is odd if it has an odd key
// hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size
public boolean isOddBalanced() {
// TODO
return false;
}
// 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-child <= size-of-smaller-child * 3)
// hint: in the helper, return -1 if the tree is not semi-perfect, otherwise return the size
public boolean isSemiBalanced() {
// TODO
return false;
}
Explanation / Answer
package chegg;
/* ***********************************************************************
* A simple BST with int keys
*
* Recall that:
* Depth of root==0.
* Height of leaf==0.
* Size of empty tree==0.
* Height of empty tree=-1.
*
* TODO: complete the functions in this file.
*
* 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, except printLeftI
* - no loops, except in printLeftI (you cannot use "while" "for" etc...)
* - 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)
*************************************************************************/
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; }
}
public void printLeftI () {
Node x = root;
while (x != null) {
System.out.println(x.key);
x = x.left;
}
}
// the number of nodes in the tree
public int size() {
return size (root, 0);
}
private static int size (Node x, int sz) {
if (x != null) {
sz = sz + 1;
sz = size (x.left, sz);
sz = size (x.right, sz);
}
return sz;
}
public int maxDepth(Node node){
if (node==null)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node.left);
int rDepth = maxDepth(node.right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
// Recall the definitions of height and depth.
// in the BST with level order traversal "41 21 61 11 31",
// node 41 has depth 0, height 2
// node 21 has depth 1, height 1
// node 61 has depth 1, height 0
// node 11 has depth 2, height 0
// node 31 has depth 2, height 0
// height of the whole tree is the height of the root
// the height of the tree (helper function is maxDepth)
public int height(Node node) {
return maxDepth(root);
}
public int totalOddKeys(Node node){
if(node==null)
return 0;
int val= (node.key%2==1) ? 0 : 1;
return val + totalOddKeys(node.left) + totalOddKeys(node.right);
}
// the number of nodes with odd keys (helper function is totalOddKeys)
public int sizeOdd() {
// TODO
return totalOddKeys(root);
}
// The next three functions compute the size of the tree at depth k.
// It should be the case that for any given k,
//
// sizeAbove(k) + sizeAt(k) + sizeBelow(k) = size()
//
// The words "above" and "below" assume that the root is at the "top".
//
// Suppose we have with size N and height H (so max depth also H).
// For such a tree, we expect
//
// sizeAboveDepth (-1) = 0
// sizeAtDepth (-1) = 0
// sizeBelowDepth (-1) = N
//
// sizeAboveDepth (0) = 0
// sizeAtDepth (0) = 1
// sizeBelowDepth (0) = N-1
//
// sizeAboveDepth (H+1) = N
// sizeAtDepth (H+1) = 0
// sizeBelowDepth (H+1) = 0
//
// the number of nodes in the tree, at exactly depth k
// include node n if depth(n) == k
public int sizeAtDepthHelper(Node node, int k, int depth){
if(root == null){
return 0;
}
if(depth == k){
return 1 + sizeAtDepthHelper(node.left, k, depth+1) + sizeAtDepthHelper(node.right, k, depth+1);
}
return sizeAtDepthHelper(node.left, k, depth+1) + sizeAtDepthHelper(node.right, k, depth+1);
}
public int sizeAtDepth(int k) {
// TODO
return sizeAtDepthHelper(root,k,0);
}
// the number of nodes in the tree, "above" depth k (not including k)
// include node n if depth(n) < k
public int sizeAboveDepthHelper(Node node, int k, int depth){
if(root == null){
return 0;
}
if(depth < k){
return 1 + sizeAboveDepthHelper(node.left, k, depth+1) + sizeAboveDepthHelper(node.right, k, depth+1);
}
else {
return sizeAboveDepthHelper(node.left, k, depth+1) + sizeAboveDepthHelper(node.right, k, depth+1);
}
}
public int sizeAboveDepth(int k) {
return sizeAboveDepthHelper(root,k,0);
}
public int sizeBelowDepthHelper(Node node, int k, int depth){
if(root == null){
return 0;
}
if(depth > k){
return 1 + sizeBelowDepthHelper(node.left, k, depth+1) + sizeBelowDepthHelper(node.right, k, depth+1);
}
else {
return sizeBelowDepthHelper(node.left, k, depth+1) + sizeBelowDepthHelper(node.right, k, depth+1);
}
}
// the number of nodes in the tree, "below" depth k (not including k)
// include node n if depth(n) > k
public int sizeBelowDepth(int k) {
// TODO
return sizeBelowDepthHelper(root,k,0);
}
// tree is perfect if for every node, size of left == size of right
// hint: in the helper, return -1 if the tree is not perfect, otherwise return the size
public boolean isPerfectlyBalancedSHelper(Node node){
if(node==null){
return true;
}
if(size(node.left,0) != size(node.right,0))
return false;
return isPerfectlyBalancedSHelper(node.left) && isPerfectlyBalancedSHelper(node.right);
}
public boolean isPerfectlyBalancedS() {
return isPerfectlyBalancedSHelper(root);
}
public boolean isPerfectlyBalancedHHelper(Node node){
if(node==null){
return true;
}
if(height(node.left) != height(node.right))
return false;
return isPerfectlyBalancedHHelper(node.left) && isPerfectlyBalancedHHelper(node.right);
}
// tree is perfect if for every node, height of left == height of right
// hint: in the helper, return -2 if the tree is not perfect, otherwise return the height
public boolean isPerfectlyBalancedH() {
// TODO
return isPerfectlyBalancedHHelper(root);
}
// tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right
// A node is odd if it has an odd key
// hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size
public boolean isOddBalanced() {
// TODO
return false;
}
// 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-child <= size-of-smaller-child * 3)
// hint: in the helper, return -1 if the tree is not semi-perfect, otherwise return the size
public boolean isSemiBalanced() {
// TODO
return false;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.