today I tried to code all the dictionary operations such as Search, Successor, Predecessor, Minimum, Maximum, Insert, Delete etc. for a Binary Search Tree data structure using the Java programming language. I would be grateful to you guys if you can review my code and suggest me some cool tricks as to how to optimize my code as well. Also it would be great if you could take a close look at my "deleteNode" method implementation and verify if it works correctly and handles all the cases or not.
// this class is used to represent the structure of a Binary Search Tree node
class BSTNode {
private String key;
private BSTNode parent;
private BSTNode leftChild;
private BSTNode rightChild;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public BSTNode getParent() {
return parent;
}
public void setParent(BSTNode parent) {
this.parent = parent;
}
public BSTNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BSTNode leftChild) {
this.leftChild = leftChild;
}
public BSTNode getRightChild() {
return rightChild;
}
public void setRightChild(BSTNode rightChild) {
this.rightChild = rightChild;
}
}
// this class provides the API for a Binary Search Tree implementation
class BSTree {
private BSTNode root; // this field refers to the root node of the Binary Search Tree
// this is the constructor for the Binary Search Tree class
public BSTree() { this.root = null; }
public void setRoot(BSTNode root) { this.root = root; }
public BSTNode getRoot() { return this.root; }
// this method does the inorder tree walk on the binary search tree
public void inorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
inorderTreeWalk(node.getLeftChild());
System.out.print(node.getKey() + " ");
inorderTreeWalk(node.getRightChild());
}
// this method does the pre-order tree walk on the binary search tree
public void preorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
System.out.print(node.getKey() + " ");
preorderTreeWalk(node.getLeftChild());
preorderTreeWalk(node.getRightChild());
}
// this method does the post-order tree walk on the binary search tree
public void postorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
postorderTreeWalk(node.getLeftChild());
postorderTreeWalk(node.getRightChild());
System.out.print(node.getKey() + " ");
}
// this method finds the node with the minimum key value in the Binary Search Tree
public BSTNode findMinimum() {
BSTNode temp = this.root;
while(temp.getLeftChild() != null) {
temp = temp.getLeftChild();
}
return temp;
}
// this method finds the node with the maximum key value in the Binary Search Tree
public BSTNode findMaximum() {
BSTNode temp = this.root;
while (temp.getRightChild() != null) {
temp = temp.getRightChild();
}
return temp;
}
// this method is used to search the Binary Search Tree for a node with the value passed in the parameter
public BSTNode searchNode(String key) {
BSTNode temp = this.root;
while(temp != null && !temp.getKey().equals(key)) {
if(key.compareTo(temp.getKey()) <= 0) {
temp = temp.getLeftChild();
} else {
temp = temp.getRightChild();
}
}
return temp;
}
// this is a private method that is useful in finding the successor of a node passed to the method
private BSTNode helpFindSuccessor(BSTNode node) {
if(node == null) {
return null;
}
while(node.getLeftChild() != null) {
node = node.getLeftChild();
}
return node;
}
// this method is used to find the successor node of the node with the given input key
public BSTNode getSuccessor(String key) {
BSTNode node = searchNode(key);
if(node == null) {
return null;
}
if(node.getRightChild() != null) {
return helpFindSuccessor(node.getRightChild());
}
BSTNode successorNode = node.getParent();
while(successorNode != null && successorNode.getLeftChild() != node) {
node = successorNode;
successorNode = successorNode.getParent();
}
return successorNode;
}
// this private method helps us in find the predecessor node in the left subtree of a binary search tree
private BSTNode helpFindPredecessor(BSTNode node) {
if(node == null) {
return null;
}
while(node.getRightChild() != null) {
node = node.getRightChild();
}
return node;
}
// this method is used to find the predecessor node of the node with the given input key
public BSTNode getPredecessor(String key) {
BSTNode node = searchNode(key);
if(node == null) {
return null;
}
if(node.getLeftChild() != null) {
return helpFindPredecessor(node.getLeftChild());
}
BSTNode predecessorNode = node.getParent();
while(predecessorNode != null && node != predecessorNode.getRightChild()) {
node = predecessorNode;
predecessorNode = predecessorNode.getParent();
}
return predecessorNode;
}
// this method inserts a node with a given value in the Binary Search Tree
public void insertNode(String value) {
// allocate a new node object for the key that needs to be inserted in the Binary Search Tree
BSTNode node = new BSTNode();
node.setKey(value);
node.setParent(null);
node.setLeftChild(null);
node.setRightChild(null);
// if the Binary Search Tree is initially empty then we make the new node to be the root of the Binary Search Tree
if(this.root == null) {
this.root = node;
} else {
BSTNode parentNode = null;
BSTNode temp = this.root;
while(temp != null) {
parentNode = temp;
int compareValue = node.getKey().compareTo(temp.getKey());
if(compareValue <= 0) {
temp = temp.getLeftChild();
} else {
temp = temp.getRightChild();
}
}
// set the new node's parent to be the parentNode object that was set in the loop
node.setParent(parentNode);
if(node.getKey().compareTo(parentNode.getKey()) <= 0) {
parentNode.setLeftChild(node);
} else {
parentNode.setRightChild(node);
}
}
}
// this method is used to delete a node from the Binary Search Tree
public void deleteNode(BSTNode node) {
// check if the node to be deleted is a valid reference, if its an invalid reference then we don't need to do anything at all
if(node == null) {
return;
}
// Case-1 : If the node to be deleted has no child references at all
if(node.getLeftChild() == null && node.getRightChild() == null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node
if(parentNode == null) {
this.root = null;
} else if (parentNode.getLeftChild() == node) {
parentNode.setLeftChild(null );
} else {
parentNode.setRightChild(null);
}
node.setParent(null);
}
// Case-2 : If the node to be deleted has one node as its child node
if(node.getLeftChild() != null && node.getRightChild() == null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node and it has a left child then make the left child of the root node as root
if(parentNode == null) {
this.root = node.getLeftChild();
} else {
// if the node to be deleted is the left child of its parent node
if(parentNode.getLeftChild() == node) {
parentNode.setLeftChild(node.getLeftChild());
} else {
parentNode.setRightChild(node.getLeftChild());
}
}
node.getLeftChild().setParent(parentNode);
node.setParent(null);
node.setLeftChild(null);
}
if(node.getLeftChild() == null && node.getRightChild() != null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node and it has a right child
if(parentNode == null) {
this.root = node.getRightChild();
} else {
// if the node to be deleted is the left child of its parent node
if(parentNode.getLeftChild() == node) {
parentNode.setLeftChild(node.getRightChild());
} else {
parentNode.setRightChild(node.getRightChild());
}
}
node.getRightChild().setParent(parentNode);
node.setParent(null);
node.setRightChild(null);
}
// Case-3 : if the node to be deleted has both a left and a right child
if(node.getLeftChild() != null && node.getRightChild() != null) {
BSTNode parentNode = node.getParent();
// first we get the successor of the node in the Binary Search Tree
BSTNode successorNode = getSuccessor(node.getKey());
BSTNode successorParent = successorNode.getParent();
BSTNode successorRightChild = successorNode.getRightChild();
// if the successor node doesn't have any right child, it obviously doesn't have any left child as its the successor node
if(successorRightChild == null) {
node.setKey(successorNode.getKey());
if(successorParent.getRightChild() == successorNode) {
successorParent.setRightChild(null);
} else {
successorParent.setLeftChild(null);
}
return;
} else {
node.setKey(successorNode.getKey());
if(successorParent.getRightChild() == successorNode) {
successorParent.setRightChild(successorRightChild);
} else {
successorParent.setLeftChild(successorRightChild);
}
}
successorRightChild.setParent(successorParent);
successorNode.setParent(null);
successorNode.setLeftChild(null);
successorNode.setRightChild(null);
}
}
}
public class BinarySearchTree {
public static void main(String[] args) {
BSTree tree = new BSTree();
tree.insertNode("D");
tree.insertNode("B");
tree.insertNode("C");
tree.insertNode("A");
tree.insertNode("F");
tree.insertNode("G");
// tree.insertNode("E");
tree.insertNode("I");
tree.insertNode("H");
tree.insertNode("J");
tree.insertNode("L");
tree.insertNode("K");
System.out.println("Inorder Tree Walk : ");
tree.inorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Preorder Tree Walk : ");
tree.preorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Postorder Tree Walk : ");
tree.postorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Node with the minimum key in the Binary Search Tree : " + tree.findMinimum().getKey());
System.out.println("Node with the maximum key in the Binary Search Tree : " + tree.findMaximum().getKey());
tree.deleteNode(tree.searchNode("D"));
System.out.println("Inorder Tree Walk after deletion of node D : ");
tree.inorderTreeWalk(tree.getRoot());
System.out.println();
}
}
