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

Question

// Complete the THREE exercises below. For each "EXERCISE" comment, add code immediately below the comment.
//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));
    }
}

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

EXERCISE 10: Modify the existing tree to remove all subtrees below depth k from

the original tree.
public static Node removeDepth (Node t, int k) {
    // TODO: Complete this method.
    return null;
}

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

// EXERCISE 11: Put the new key into the tree (modifying the tree).
// If the key already exists in the tree, do nothing.
// You can assume that the tree is in sorted order before the put operation.
// The tree must be in sorted order after the put operation.
public static Node put (Node t, int key) {
    // TODO: Complete this method.
    return null;
}

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

// EXERCISE 12: Test whether the tree contains the key.
// You can assume that the tree is in sorted order before the put operation.
public static boolean contains (Node t, int key) {
    // TODO: Complete this method.
    return false;
}
}

Explanation / Answer

public static Node removeDepth (Node t, int k) {
{
//checking for empty node
if(t == null){
return new Node(false, null);
}
//if exact node found then reove it
if(Integer.parseInt(t.key) == k)
return new Node(true, null);
//otherwise remove remove left children
Node result = removeDepth(t.left, k);
if(result.key.length()>0) { //otherwise remove right childdren
result = removeDepth(t.right, k);
t.right = null;
} else t.left = null;
return new Node(result.key, t);
}
}

------------------------------------------------------
public static Node put (Node t, int key) {
// TODO: Complete this method.
if ( root == null ) //if empt create new one
{
root = new Node( t, key );
}
else
{
root.put( t, key ); //otherwise modify
}
return null;
}

-----------------------------------
public static boolean contains (Node t, int key) {
if(t == null) return false; //checking for empty tree
return t.contains(key); //it will returns true of contsind ..otherwise false
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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