// Complete the THREE exercises below. For each \"EXERCISE\" comment, add code i

ID: 666182 • Letter: #

Question

// Complete the THREE exercises below. For each "EXERCISE" comment, add code immediately below the comment.
//
// 2. You MUST NOT edit the IDEA/SBT configuration/tests. Altering it in your submission will result in 0 points for this assignment.
//
// This class represents operations on simple Binary Search Trees (BST) with integer keys and no values, i.e., a set of integers.
//
// DO NOT change the name or type of any function (the first line of the function)

// All of the methods in this class are static (and mostly recursive).
// These methods could naturally appear inside Node.java also.
//
// This code is not representative of the object-oriented style of programming, but is concise and allows null to be used to represent leaf nodes.

public class NodeOps {
public static String toString (Node t) {
    if (t == null) {
      return "null";
    } else {
      return "new Node (" + t.key + ", " + toString (t.left) + ", " + toString

(t.right) + ")";
}
}

public static String toStringIndent (Node t, String indent) {
    if (t == null) {
      return indent + "null";
    } else {
      String indent2 = indent + " ";
      return indent + "new Node ( " + indent2 + t.key + ", " + toStringIndent

(t.left, indent2) + ", " + toStringIndent (t.right, indent2) + " " + indent + ")";
}
}

public static Node copy (Node n) {
    if (n == null) {
      return null;
    } else {
      return new Node (n.key, copy (n.left), copy (n.right));
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// 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

// EXERCISE 4: The method "sizeAtDepth" is described above.
public static int sizeAtDepth (Node t, int k) {
// TODO: Complete this method.
return -1;
}

// EXERCISE 5: The method "sizeAboveDepth" is described above.
// The number of nodes in the tree "above" depth k (not including k)
// include node n if depth(n) < k.
public static int sizeAboveDepth (Node t, int k) {
// TODO: Complete this method.
return -1;
}

// EXERCISE 6: The method "sizeBelowDepth" is described above.
// The number of nodes in the tree "below" depth k (not including k)
// include node n if depth(n) > k.
public static int sizeBelowDepth (Node t, int k) {
// TODO: Complete this method.
return -1;
}

Explanation / Answer

public int sizeAtDepth(int k) { return sizeAtDepth(k, root, 0); }

    private int sizeAtDepth(int k, Node x, int depth){
    if (x == null) return 0;
    return sizeAtDepth(k, x.right, depth + 1) + sizeAtDepth(k, x.left, depth + 1) + (k == depth ? 1 : 0);
    }

    // the number of nodes in the tree, above depth k (not including k)
    public int sizeAboveDepth(int k) { return sizeAboveDepth(k, root, 0); }

    private int sizeAboveDepth(int k, Node x, int depth){
    if (x == null) return 0;
    return sizeAboveDepth(k, x.left, depth + 1) + sizeAboveDepth(k, x.right, depth + 1) + (k > depth ? 1 : 0);
    }

    // the number of nodes in the tree, below depth k (not including k)
    public int sizeBelowDepth(int k) { return sizeBelowDepth(k, root, 0); }

    private int sizeBelowDepth(int k, Node x, int depth){
    if (x == null) return 0;
    return sizeBelowDepth(k, x.left, depth + 1) + sizeBelowDepth(k, x.right, depth + 1) + (k < depth ? 1 : 0);
    }

Navigate

// Complete the THREE exercises below. For each \"EXERCISE\" comment, add code i

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

// Complete the THREE exercises below. For each \"EXERCISE\" comment, add code i

Question

Explanation / Answer

Related Questions

Navigate