Given a standard BST implementation, write an algorithm that does the following:

Question

Given a standard BST implementation, write an algorithm that does the following: given a
sorted array of keys (elements), add them to a BST in such a way that the resulting tree is a
complete
2
binary tree. Implement the algorithm in Java using the sample BSTSet code posted
online. Your implementation must be in the form of the following class:
public class BSTCreator
{
// PRECONDITION: The given array is sorted.
// Returns a complete BST containing the data in the array.
public static <T extends Comparable<? super T>> BSTSet<T>
createCompleteTree(T[] arr)
{
// TODO
return null;
}
}
Please submit your BSTCreator.java file on Blackboard.
The class skeleton above is provided online as well. (Do not worry too much about the annoying
type parameter <T extends Comparable<? super T>>, it just indicates that the BST can call
compareTo on the keys.)

Explanation / Answer

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) { if (start > end) return NULL; // same as (start+end)/2, avoids overflow int mid = start + (end - start) / 2; BinaryTree *leftChild = sortedListToBST(list, start, mid-1); BinaryTree *parent = new BinaryTree(list->data); parent->left = leftChild; list = list->next; parent->right = sortedListToBST(list, mid+1, end); return parent; } BinaryTree* sortedListToBST(ListNode *head, int n) { return sortedListToBST(head, 0, n-1); } package setstuff100; import java.util.*; 5 /** * Simple binary search tree implementation of a set. Operations are O(log n) * in average case and O(n) in the worst case for unbalanced trees. * @author Owen Astrachan */ 10 public class BSTSet implements ISimpleSet { private class TreeNode { 15 E info; TreeNode left; TreeNode right; TreeNode parent; 20 TreeNode(E element, TreeNode lptr, TreeNode rptr, TreeNode p) { info = element; left = lptr; right = rptr; 25 parent = p; } } private int mySize; 30 private TreeNode myRoot; public BSTSet() { mySize = 0; 35 myRoot = null; } public int size() { return mySize; 40 } public boolean add(E element) { if (myRoot == null) { myRoot = new TreeNode(element, null, null, null); 45 mySize++; return true; } TreeNode root = myRoot; 50 while (root != null) { int comp = root.info.compareTo(element); if (comp == 0) return false; if (comp > 0) { 55 if (root.left == null) { root.left = new TreeNode(element, null, null, root); mySize++; return true; } else { 60 root = root.left; } } else { if (root.right == null) { root.right = new TreeNode(element, null, null, root); 65 mySize++; return true; } else { root = root.right; } 70 } } // can never reach here return false; Dec 05, 11 8:46 BSTSet.java Page 1/3 75 } public boolean remove(E element) { TreeNode root = myRoot; while (root != null) { 80 int comp = root.info.compareTo(element); if (comp == 0) { mySize--; remove(root); return true; 85 } else if (comp > 0) { root = root.left; } else { root = root.right; } 90 } return false; } private void remove(TreeNode root) { 95 if (root.left == null && root.right == null) { // removing leaf if (root.parent == null) { // removing root? myRoot = null; // tree now empty } else { 100 if (root.parent.left == root) { root.parent.left = null; } else { root.parent.right = null; } 105 } } else if (root.left == null || root.right == null) { // one child, not two TreeNode child = root.left; // only child is left? if (root.left == null) { // nope, it’s right 110 child = root.right; } if (root.parent == null) { // new root myRoot = child; } else if (root.parent.left == root) { 115 root.parent.left = child; } else { root.parent.right = child; } child.parent = root.parent; 120 } else { // removing node with two children TreeNode successor = root.right; if (successor.left == null) { root.info = successor.info; root.right = successor.right; 125 if (successor.right != null) { successor.right.parent = root; } } else { // immediate right child of removed node has a left child 130 while (successor.left != null) { successor = successor.left; } root.info = successor.info; successor.parent.left = successor.right; 135 if (successor.right != null) { successor.right.parent = successor.parent; } } } 140 } private TreeNode successor(TreeNode t) { if (t == null) return null; // no successor 145 else if (t.right != null) { t = t.right; Dec 05, 11 8:46 BSTSet.java Page 2/3 Printed by Owen L. Astrachan Monday December 05, 2011 BSTSet.java 3/12 while (t.left != null) { t = t.left; } 150 return t; } else { TreeNode parent = t.parent; while (parent != null && parent.right == t) { t = parent; 155 parent = t.parent; } return parent; } } 160 public boolean contains(E element) { TreeNode root = myRoot; while (root != null) { int comp = root.info.compareTo(element); 165 if (comp == 0) return true; else if (comp > 0) { root = root.left; } else { 170 root = root.right; } } return false; } 175 public Iterator iterator() { return new TreeIterator(myRoot); } 180 private class TreeIterator implements Iterator { private TreeNode myCurrent; private TreeNode myPrevious; 185 public TreeIterator(TreeNode root) { while (root.left != null) { root = root.left; } 190 myCurrent = root; myPrevious = null; } public boolean hasNext() { 195 return myCurrent != null; } public E next() { E data = myCurrent.info; 200 myPrevious = myCurrent; myCurrent = successor(myCurrent); return data; } 205 public void remove() { if (myPrevious == null) { throw new IllegalStateException( "cannot remove, no valid next call"); } 210 BSTSet.this.remove(myPrevious); myPrevious = null; mySize--; } } 215 }

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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