I've added some methods to a basic BST implementation for integers - if anyone can point out some ways that this could be written in a more efficient or clean manner, please let me know.
public class BST {
/*
* 1) Node inner class
*/
private class Node {
int data;
Node leftChild, rightChild;
public Node(int num, Node left, Node right) {
this.data = num;
this.leftChild = left;
this.rightChild = right;
}
}
// 2) Variables
private Node root = null; // every binary search tree object will be assigned a root node = null
private int nodeCount = 0;
// 3) Methods: size
public int size() {
return nodeCount;
}
// 4) Methods: isEmpty
public boolean isEmpty() {
return (root == null); // if the root of the BST is null (we haven't added any nodes) then the BST is empty
}
// 5) Methods: contains (recursive), SEARCH
public boolean treeContains(int info) {
return treeContains(root, info);
}
public boolean treeContains(Node node, int info) {
if (node == null) return false; // corner case: if tree is null, but also BASE CASE
// SEARCHING, but looking for a number so we can use O log(n) time
if (info > node.data) { // go to the right
return treeContains(node.rightChild, info);
}
else if (info < node.data) {
return treeContains(node.leftChild, info);
}
else { // either node has bigger or smaller data or this case: it is equal
return true;
}
}
// 6) Methods: add
public boolean add(int newData) {
if (treeContains(newData)) return false;
else {
root = add(root, newData); // NOTE: this works but why can't it just be add(root,newdata) without the "root = " ?
nodeCount++;
return true;
}
}
public Node add(Node node, int newData) {
if (node == null) {
node = new Node(newData, null, null); // NOTE: how does this add a node? it doesn't place it anywhere? it just exists somewhere? i mean i understand that by then we're pointing to a space that is null but still
}
else if (newData > node.data) {
node.rightChild = add(node.rightChild, newData);
}
else { // else if newData is less or equal to node data
node.leftChild = add(node.leftChild, newData);
}
return node;
}
// 7) Methods: remove
// look up node to be removed, set it to null, recursive
public boolean remove(int newData) {
if (!treeContains(newData)) return false; // will null BST's fall under this ???
else {
root = remove(root,newData); // NOTE: why do we need to have root = remove(root, newData) ??? instead of just remove..
nodeCount--;
return true;
}
}
public Node remove(Node node, int newData) {
if (node.data == newData) { // if we find the node we want to delete
// 3 SCENARIOS - the node can be a leaf, can have 1 or 2 children
// leaf node
if (node.leftChild==null && node.rightChild== null) {
node = null;
}
// node has left child only
else if (node.leftChild !=null && node.rightChild == null) {
node.data = node.leftChild.data; // left child is now node
node.leftChild = null;
}
// node has right child only
else if (node.leftChild==null && node.rightChild!=null) {
Node temp = node.rightChild; // trying another way of switching nodes & deleting
node.rightChild = null;
node.data = temp.data;
}
// node has both children
else {
Node temp = findMin(node.rightChild);
node.data = temp.data; // switch data
node.rightChild = remove(node.rightChild, temp.data); // remove the findMin node, originally node.RC = remove...
}
}
else if (newData < node.data) {
node.leftChild = remove (node.leftChild, newData);
}
else { // if newData > node.data
node.rightChild = remove(node.rightChild, newData);
}
return node;
}
// Helper method to find the leftmost node (which has the smallest value)
private Node findMin(Node node) {
while (node.leftChild != null)
node = node.leftChild;
return node;
}
// 8) Methods: In order tree traversal
public void traverseInOrder(Node node) {
if (node == null) return;
traverseInOrder(node.leftChild);
System.out.print(node.data + " ");
traverseInOrder(node.rightChild);
}
// 9) Methods: Pre order tree traversal
public void traversePreOrder(Node node) {
if (node == null) return;
System.out.print(node.data + " ");
traversePreOrder(node.leftChild);
traversePreOrder(node.rightChild);
}
// 10) Methods: Post order tree traversal
public void traversePostOrder(Node node) {
if (node == null) return;
traversePostOrder(node.leftChild);
traversePostOrder(node.rightChild);
System.out.print(node.data + " ");
}
// RUN METHODS
public static void main(String[] args) {
BST tree1 = new BST();
tree1.add(10);
tree1.add(7);
tree1.add(5);
tree1.add(8);
tree1.add(20);
tree1.add(15);
tree1.add(25);
tree1.traverseInOrder(tree1.root);
System.out.println( "\nSize of tree is: " + tree1.size() );
System.out.println( "Root of tree is: " + tree1.root.data );
System.out.println( "Min num of tree is: " + tree1.findMin(tree1.root).data );
System.out.println( "Does the tree contain the #5 ? " + tree1.treeContains(5) );
tree1.remove(8);
tree1.remove(20);
tree1.traverseInOrder(tree1.root);
System.out.println( "\nSize of tree is: " + tree1.size() );
}
}
Thank you!!
