Overview, write methods to delete nodes from a binary search tree (BST.) You will need to preserve the BST properties at all times: that from a given node, the left subtree will contain only nodes which are lower and the right subtree will contain only nodes which are higher. For this purpose, you will need to create some methods first which will let you add a node to the furthest left or right position under a given node. These will allow you to relocate the children of nodes which are deleted, while making sure that they are in a place that is legal under the BST property.

Objectives

• Practice creating a class
• Practice with BSTs (binary search trees)
• Practice with recursion
• Apply test cases to your program

Set-up

1. Start Intellij
2. At the Welcome Window click Create New Project

1. In the New Project window
   1. Type the name of the project in theProject name: textbox.
      1. Name your projectBST Delete
2. Download the starter code from the course public folder (public/18L) and save it in the src directory of your new project.

Implementation

The starter code includesBinarySearchTree.java,Data.java, andTreeApp.java. You should not change anything inData.java, orTreeApp.java but you can run the main method of TreeApp.java to test your work. Your task will be to complete several methods inBinarySearchTree.java.

public void addToFarRight( Node n, Node subtree )

Insertsubtree at the furthest right position undern. This can be done iteratively by settingn to its right child repeatedly in a loop until there is no right child, or recursively by calling onn's right child until you reach a node that has no right child. In either case, oncen has no right child, setsubtree to be the right child ofn andn to be the parent ofsubtree. This allows you to find a new place for the children of nodes which will be removed in the later methods.

public void addToFarLeft( Node n, Node subtree )

Insertsubtree at the furthest left position undern. This can be done iteratively by settingn to its left child repeatedly in a loop until there is no left child, or recursively by calling onn's left child until you reach a node that has no left child. In either case, oncen has no left child, setsubtree to be the left child ofn andn to be the parent ofsubtree. This allows you to find a new place for the children of nodes which will be removed in the later methods.

public void removeRight( Node parent, Node n )

Remove a noden which is the right child ofparent. Ifn has both a left and right child, the left child should be added to the far left of the right child, and the right child should taken's place as the right child ofparent. Ifn has only a right child, the right child should taken's place. Ifn has only a left child, the left child should taken's place. Ifn has no children,parent's right child should be set to null. Don't forget to change the parent variable of whichever node replacesn.

public void removeLeft( Node parent, Node n )

Remove a noden which is the left child ofparent. Ifn has both a left and right child, the right child should be added to the far right of the left child, and the left child should taken's place as the left child ofparent. Ifn has only a right child, the right child should taken's place. Ifn has only a left child, the left child should taken's place. Ifn has no children,parent's left child should be set to null. Don't forget to change the parent variable of whichever node replacesn.

public void removeRoot()

Remove the root node and relocate its children's subtrees to maintain the BST properties. If the root has a left and right child, the right child should be added to the far right of the left child, and the left child should be made the root. If the root has only a right child, the right child should be made the root and its parent set to null. If the root has only a left child, the left child should be made the root and its parent set to null. If the root has no children, the root can be set to null. Don't forget to change the parent variable tonull for whichever node replaces the root.

public void removeNode( Node n )

Detect whethern is the root of the tree, a left child of its parent, or a right child of its parent, and then call the correct method to removen in whichever situation. Decrease the tree's size by 1.

Assessment

Criteria (BinarySearchTree.java)	Points
Program compiles without error	5
remove leaf node	10
remove node with only left child	10
remove node with only right child	10
remove node with both children	10
remove root with only right child	10
remove root with only left child	9
remove root with both children	9
remove all nodes in tree of size 1	9
remove all nodes in tree of size 4	9
remove all nodes in tree of size 16	9
Total	100

//++++++++++++++++++++++++ TreeApp +++++++++++++++++++++++++++++ import java.util.*; /** * TreeApp - the main class for controlling the application code. * * The application semantics including the graphics generated * by the app are controlled from this class. * * @author rdb */ public class TreeApp { //--------------------- class variables private static TreeApp treeApp; // the singleton TreeApp public static Random rng = null; //--------------------- instance variables ------------------------- public ArrayList _list; public BinarySearchTree _bst = null; //--- data generation constants with package access int dataSize = 8; int minDataSize = 0; int maxDataSize = 20; int defaultDataSize = 8; int rngSeed = 2; // random seed int maxSeed = 16; // arbitrary number //--- subset constants private int subsetMin = 30; // arbitrary; all values are 0, 100 private int subsetMax = 70; //---------------------- constructor -------------------------------- /** * */ public TreeApp( ) { treeApp = this; } //----------------------- treeApp() -------------------------- /** * Static application accessor. * @return TreeApp */ public static TreeApp treeApp() { return treeApp; } //---------------------- makeData() ----------------------------- /** * Update list size and generate a new list of that size. * @param sz int size */ public void makeData( int sz ) { this.dataSize = sz; _list = generateData( this.dataSize, this.rngSeed ); _bst = new BinarySearchTree(); for ( Data d: _list ){ _bst.add( d ); } } /** * Show results to "user". Print to standard output. * @param msg String string to print */ public void showResults( String msg ) { System.out.println( msg ); } //------------------- printTree( String ) -------------------- /** * Print the tree with given title. * @param title String */ public void printTree( String title ) { String dashes = " ------------------------ "; System.out.println( " " + dashes + title + dashes ); if ( _bst == null || _bst.size() == 0 ) System.out.println( "---Empty---" ); else { System.out.println( _bst ); System.out.println( "Tree has " + _bst.size() + " nodes." ); } } //------------------- generateData --------------------------------- /** * Generate data for a new tree. Arguments are * numItems -- number items to generate * seed -- random number seed; -1 means let system pick it. * @param numItems int * @param seed int * @return ArrayList */ static ArrayList generateData( int numItems, int seed ) { ArrayList dl = new ArrayList(); ArrayList keys = new ArrayList(); if ( rng == null ) rng = new Random(); rng.setSeed(seed); String letters = "abcdefghijklmnopqrstuvwxyz"; StringBuffer keybuf = new StringBuffer( "12" ); while ( dl.size() < numItems ) { // generate a key char letter1 = letters.charAt( rng.nextInt( letters.length() ) ); char letter2 = letters.charAt( rng.nextInt( letters.length() ) ); keybuf.setCharAt( 0, letter1 ); keybuf.setCharAt( 1, letter2 ); String key = keybuf.toString(); if ( ! keys.contains( key ) ) { // generate a value from 0 to 99 int val = rng.nextInt( 100 ); dl.add( new Data( key, val ) ); keys.add( key ); } } return dl; } /** * Ensure that BST has all correct values. * */ public String validateTreeData(){ String ret = ""; for( Data d: _list ){ if(_bst.find( d.key )==null) ret += d.key + ", "; } if(ret.equals("")) return ret; else return ret.substring(0, ret.length()-2); } /** * Ensure that BST has all correct values. * */ public String validateTreeOrder(){ String ret = ""; HashSet outOfOrder = new HashSet(); validateSubtree(_bst.root(), outOfOrder); for(String s: outOfOrder) ret += s + ", "; if(ret.equals("")) return ret; else return ret.substring(0, ret.length()-2); } private void validateSubtree( BinarySearchTree.Node n, HashSet result){ if(n==null) return; validateSubtree(n.left, result); validateSubtree(n.right, result); validateSubtree(n.left, n.data.key, true, result); validateSubtree(n.right, n.data.key, false, result); } private void validateSubtree( BinarySearchTree.Node n, String rootKey, boolean isLeft, HashSet result ){ if(n==null) return; if(isLeft && rootKey.compareTo(n.data.key) <= 0) result.add(n.data.key); if(!isLeft && rootKey.compareTo(n.data.key) >= 0) result.add(n.data.key); validateSubtree(n.left, rootKey, isLeft, result); validateSubtree(n.right, rootKey, isLeft, result); } //------------------ checkParentLinks( BST ) ---------------------- /** * For a complete check of parent links, the root parent should be * checked to make sure it is null. */ String checkParentLinks( ) { BinarySearchTree.Node root = _bst.root(); if ( root != null && root.parent != null ) { System.err.print( "parent( root ) != null. -> " + root.parent.data ); } return checkParentLinks( root ); } //--------------------- checkParentLinks ------------------------- /** * Recursively check that the parent reference of both node's children * reference the node. Print to System.err, if anything is bad. * @param n Node */ String checkParentLinks( BinarySearchTree.Node n ) { String ret = ""; if ( n == null ) return ret; if ( n.left != null ) { if ( n.left.parent != n ){ ret += n.left.data.key; } ret += checkParentLinks( n.left ); } if ( n.right != null ) { if ( n.right.parent != n ){ ret += n.right.data.key; } ret += checkParentLinks( n.right ); } return ret; } //----------------- main ------------------------------------------- /** * Convenience method to execute BSTDeleteApp.main. * @param args String[] */ public static void main( String[] args ) { TreeApp t = new TreeApp( ); for(int i = 1; i < 64; i*=2){ t.makeData(i); t.printTree("current tree"); //remove nodes boolean removedAll = true; while(!t._list.isEmpty()){ int r = t.rng.nextInt( t._list.size() ); String key = t._list.get(r).key; t._list.remove(r); String before = t._bst.toString(); t._bst.delete( key ); String missing = t.validateTreeData(); String outOfOrder = t.validateTreeOrder(); String badParents = t.checkParentLinks(); boolean printTree = false; if( t._bst.size()!=t._list.size() || !missing.equals("") || !outOfOrder.equals("") || !badParents.equals("") || t._bst.find(key)!=null ){ removedAll = false; printTree = true; t.showResults("----------Invalid tree after deleting " + key); } if( t._bst.find(key)!=null ){ removedAll = false; printTree = true; t.showResults("----------Tree still contained " + key); } if( t._bst.size()!=t._list.size() ){ removedAll = false; printTree = true; t.showResults("----------Expected size: " + t._list.size() + " BST size: " + t._bst.size()); } if( !missing.equals("")){ removedAll = false; printTree = true; t.showResults("----------Cannot find: " + missing + " (possibly due to being out of order)"); } if( !outOfOrder.equals("")){ removedAll = false; printTree = true; t.showResults("----------Out of order: " + outOfOrder); } if( !badParents.equals("")){ removedAll = false; printTree = true; t.showResults("----------Nodes with incorrect parents: " + badParents); } if(printTree){ System.out.println("********** Original tree ********** " + before + "***********************************"); System.out.println("******* Tree after deletion ******* " + t._bst.toString() + "***********************************"); System.out.println(); System.out.println(); } } if(removedAll) t.showResults("----------Successfully removed all nodes."); } } }

/** * Data - the object to be stored in the data structure. It has * String key -- the key used in the Comparable interface * int value -- a stub representing other data * @author mdb * * Edited by rdb * Last edit: * 03/16/14 rdb Make checkstyle-compatible */ public class Data { //------------ instance variables ---------------------------- String key; // key must be unique int value; //------------------ constructor ----------------------------- /** * Construct a Data object from its components. * * @param k String key field * @param v int represents data associated with key */ public Data( String k, int v ) { key = k; value = v; } //-------------------- getKey() ------------------------- /** * Get the key. * * @return String the key field */ public String getKey() { return key; } //-------------------- toString() ------------------------ /** * Return a string representation for the object. * @return String the representation */ public String toString() { return key + ":" + value ; } //------------------- compareTo ----------------------------------- /** * Compare this object to another Data object based on the key field. * * @param other Data comparing object * @return int <0, 0, >0 based on ordering of this to that */ int compareTo( Data other ) { return key.compareTo( other.key ); } } 

import java.util.*; import java.io.*; public class BinarySearchTree { //-------------------- instance variables --------------------- private Node _root; private int _size; //-------------------- constructors -------------------------- /** * Construct an empty tree with no nodes. */ public BinarySearchTree() { _root = null; } /** * Construct a tree with a root . * @param rootData Data */ public BinarySearchTree( Data rootData ) { this(); _root = new Node( rootData ); } //+++++++++++++++++++++++ inner class Node ++++++++++++++++++++++ /** * The Node class does not have to be seen outside this class, so * it is private. */ static public class Node { //-------------- instance variables --------------------------- Data data; Node left; Node right; Node parent; //--------------- constructor -------------------------------- /** * Constructor. * @param d Data */ public Node( Data d ) { data = d; left = null; right = null; parent = null; } } ///////////////////////////////////////////////////////////////// // DO NOT CHANGE ANY CODE BEFORE THIS POINT ///////////////////////////////////////////////////////////////// //---------------------- addToFarRight( node, node ) ---------------- /** * Add subtree Node as the right most descendant of the 1st argument. * @param n Node root of tree to which subtree must be added * @param subtree Node subtree to be added to far right of subtree */ public void addToFarRight( Node n, Node subtree ) { // YOUR CODE HERE } //----------------------- addToFarLeft( Node, Node ) -------------- /** * Add subtree Node as the left most descendant of the 1st argument. * @param n Node root of tree to which subtree must be added * @param subtree Node subtree to be added to far left of subtree */ public void addToFarLeft( Node n, Node subtree ) { // YOUR CODE HERE } //-------------------- removeRight( Node, Node ) ------------------- /** * Remove a node that is the right child of its parent. * @param parent Node * @param n Node */ private void removeRight( Node parent, Node n ) { // YOUR CODE HERE } //-------------------- removeLeft( Node, Node ) -------------------- /** * Remove a node that is the left child of its parent. * @param parent Node * @param n Node */ private void removeLeft( Node parent, Node n ) { // YOUR CODE HERE } //-------------------- removeRoot( ) ------------------------------ /** * Remove the root node. */ private void removeRoot() { // YOUR CODE HERE } //-------------------- removeNode( Node ) ------------------------ /** * Remove a specific node from the tree. Decrease the size. * @param n Node node to be deleted */ void removeNode( Node n ) { // YOUR CODE HERE } ///////////////////////////////////////////////////////////////// // DO NOT CHANGE ANY CODE AFTER TO THIS POINT ///////////////////////////////////////////////////////////////// //-------------------- delete( Data ) ------------------------------ /** * Find the node in the tree whose data field contains a key that * matches the key contained in the Data parameter. * @param d Data * @return Data */ public Data delete( Data d ) { return delete( d.key ); } //-------------------- delete( String ) ---------------------------- /** * Find the node in the tree whose data field contains a key that * matches the string passed as an argument. * @param k String * @return Data */ public Data delete( String k ) { Data foundData = null; Node found = findNode( k ); if ( found != null ) { foundData = found.data; removeNode( found ); } return foundData; } //--------------------- root() ---------------------------------- /** * Return root of the tree; this is package access so that DrawPanel * can do a prefix walk of the tree. Would be better to have multiple * iterators. * @return BinarySearchTree.Node */ BinarySearchTree.Node root() { return _root; } //-------------------- find( String ) ------------------------- /** * Given a key value, search the tree to find the node that has * that key value, if it exists. * * Return the Data object from the node or null * @param key String * @return Data */ public Data find( String key ) { Data found = null; Node cur = _root; while ( cur != null && found == null ) { int cmp = key.compareTo( cur.data.key ); if ( cmp == 0 ) found = cur.data; else if ( cmp < 0 ) cur = cur.left; else cur = cur.right; } return found; } //-------------------- findNode( String ) ------------------------- /** * Given a key value, search the tree to find the node that has * that key value, if it exists. * * Return the Data object from the node or null. * @param key String * @return Node */ public Node findNode( String key ) { Data found = null; Node cur = _root; while ( cur != null && found == null ) { int cmp = key.compareTo( cur.data.key ); if ( cmp == 0 ) found = cur.data; else if ( cmp < 0 ) cur = cur.left; else cur = cur.right; } return cur; } //--------------------- add ----------------------------------- /** * Add a node to the tree in its proper position determined by the * "key" field of the Data object. This method uses the addNode * recursive utility method. * @param data Data */ public void add( Data data ) { Node newNode = new Node( data ); if ( _root == null ) _root = newNode; else addNode( _root, newNode ); _size++; } //------------------ addNode( Node, Node ) ----------------------- /** * A recursive method to add a new Node (2nd argument) to the subtree * rooted at the first argument. * @param parent Node root of tree into which the new Node must go. * @param newOne Node Node to be added */ private void addNode( Node parent, Node newOne ) { if ( newOne.data.compareTo( parent.data ) < 0 ) { if ( parent.left != null ) addNode( parent.left, newOne ); else { parent.left = newOne; newOne.parent = parent; } } else { if ( parent.right != null ) addNode( parent.right, newOne ); else { parent.right = newOne; newOne.parent = parent; } } } //-------------------------- size() ------------------------- /** * Return tree size. * @return int */ public int size() { return _size; } //-------------------------- toString() ------------------------- /** * Generate a string representation of the tree. * @return String */ public String toString() { return toString( _root, " ", " " ) ; } /** * Recursively generate a string representation for a Node of a tree. * indent is increased for increasing depth. * branch is a short character string that prefixes each node indicating * whether this node is a left (L) or right (R) child of its parent. * @param n Node subtree root * @param indent String * @param branch String * @return String */ private String toString( Node n, String indent, String branch ) { String s = ""; if ( n != null ) { String prefix = indent.substring( 0, indent.length() - 2 ) + branch; s += prefix + n.data.toString() + " "; if ( n.left != null ) s += toString( n.left, indent + " ", "L " ); if ( n.right != null ) s += toString( n.right, indent + " ", "R " ); } return s; } }