package cs1501_p1;

public class BST> implements BST_Inter { private BTNode root = null;

public void put(T key) // Add a new key to the BST { BTNode node = root; this.put(node, key); }

private void put(BTNode node, T key) { BTNode newNode = new BTNode(key); if (node == null) { root = newNode; //put if root is null return; } if (key.compareTo(node.getKey()) > 0) //find the position of newNode in right branch { if (node.getRight() != null) { node = node.getRight(); this.put(node, key); //recursion } else { node.setRight(newNode); //put the key in the null } } else if (key.compareTo(node.getKey())

public boolean contains(T key) // Search the BST for a key, return true if the key is present, false if it is not. { BTNode node = root; while (node != null) { if (key.compareTo(node.getKey()) > 0) { node = node.getRight(); } else if (key.compareTo(node.getKey())

public void delete(T key) // Remove a key from the BST { if (root == null) { return; }

BTNode node = root; BTNode parent = null;

while (node != null && key.compareTo(node.getKey()) != 0) { parent = node; if (key.compareTo(node.getKey()) child = node.getLeft() != null ? node.getLeft() : node.getRight(); if (parent == null) { root = child; } else if (parent.getLeft() == node) { parent.setLeft(child); } else { parent.setRight(child); } } else // Case 3: Node with two children { BTNode successor = getSuccessor(node); delete(successor.getKey()); } }

private BTNode getSuccessor(BTNode delNode) { BTNode successor = delNode; BTNode successorParent = null; BTNode current = delNode.getRight();

while (current != null) { successorParent = successor; successor = current; current = current.getLeft(); } if (successor != delNode.getRight()) //if successor is not the right side of the delnode { successorParent.setLeft(successor.getRight()); successor.setRight(delNode.getRight()); } successor.setLeft(delNode.getLeft()); return successor; }

public int height() // Return the height of the BST { BTNode node = root; return height(node); }

private int height(BTNode node) { if (node == null) { return 0; } return 1 + Math.max(height(node.getLeft()), height(node.getRight())); }

public boolean isBalanced() // Return true if the BST is height-balanced { BTNode node = root; return isBalanced(node); }

private boolean isBalanced(BTNode node) { if (node == null) { return true; } isBalanced(node.getLeft()); isBalanced(node.getRight()); int leftHeight = height(node.getLeft()); int rightHeight = height(node.getRight()); int dif = Math.abs(leftHeight - rightHeight); return dif

public String inOrderTraversal() // Perform an in-order traversal of the tree and produce a String containing the keys in ascending order, separated by ':''s. { BTNode node = root; String res = this.inOrderTraversal(node); return res.substring(0, res.length() - 1); }

private String inOrderTraversal(BTNode node) { if (node == null) { return ""; }

String s = ""; s += inOrderTraversal(node.getLeft()); s += node.getKey() + ":"; s += inOrderTraversal(node.getRight()); return s; }

public String serialize() { return "R(" + root.getKey() + ")," + serialize(root); }

private String serialize(BTNode node) { if (node == null) { return "X(NULL)"; } if (node.getLeft() == null && node.getRight() == null) { return "L(" + node.getKey() + ")"; } if (node.getLeft() == null || node.getRight() == null) { return (node.getLeft() != null ? serialize(node.getLeft()) : serialize(node.getRight())) + "," + "X(" + node.getKey() + ")"; } String left = serialize(node.getLeft()); String right = serialize(node.getRight()); return left + "," + "I(" + node.getKey() + ")," + right; }

public BST_Inter reverse() { BST reversed = new BST(); reversed.root = reverse(this.root); return reversed; }

private BTNode reverse(BTNode reversed) { if (reversed == null) { return null; } BTNode newNode = new BTNode(reversed.getKey()); newNode.setLeft(reverse(reversed.getRight())); newNode.setRight(reverse(reversed.getLeft())); return newNode; } } fix the code above tester:

output:

Expected: R(10),I(5),L(2),X(NULL),I(37),X(NULL),L(45) Actual: R(45),X(NULL),I(2),L(5),I(10),X(NULL),I(37),X(NULL),I(45),X(NULL)

- serialize(): Perform a pre-order traversal of the BST in order to produce a String representation of the BST. The reprsentation should be a comma separated list where each entry represents a single node. Each entry should take the form: type(key). You should track 4 node types: - R : The root of the tree - I : An interior node of the tree (e.g., not the root, not a leaf) - L: A leaf of the tree - x : A stand-in for a null reference For each node, you should list its left child first, then its right child. You do not need to list children of leaves. The x type is only for nodes that have one valid child. The key for an x node should be NULL (all caps). Consider the following: Calling on this tree should return the String "R(10), I(5), L(2), X(NULL), I(37), X(NULL),L(45)" : Produce a deep copy of the BST that is reversed (i.e., left children hold keys greater than the current key, right children hold keys less than the current key). We do not expect any BSTs returned by to have working put(), or delete() methods, this is fine. Note that a correct implementation of will be needed to verify the results of reverse()