Code:
// 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();
}
}
Output:
Execute and get the output.
More Java Programs:
