Search
Searching for a key in Binary Search Tree (BST). Time complexity O(h) where h being the height of the tree. To leverage the best of BST search, the BST has to be height balanced.
/**
* Search in binary search tree.
* Time complexity - O(h), h being height of the tree.
* @param root
* @param key
* @return
*/
public Node search(Node root, int key){
/* If node null return null */
if(null == root){
return null;
}
/* Compare the key with the node */
if(key == root.getValue()){
return root;
}
/* If key is less than node's value, continue search in left tree */
if(key < root.getValue()){
return search(root.getLeft(), key);
}
/* If key is greater than node's value, continue search in right tree */
return search(root.getRight(), key);
}
Insertion
Inserting a node into a BST. Inserting always happens at the leaf node and hence the time complexity is O(h) where h is the height of the tree.
/**
* Insert node into a BST.
* Time complexity - O(h), h being the height of the tree.
* @param root
* @param value
* @return
*/
public Node insertNode(Node root, int value){
/* If the node is leaf, then create a node and attach */
if(null == root){
return new Node(value, null, null);
}
/* Traverse to the leaf node*/
if(value < root.getValue()){
root.setLeft(insertNode(root.getLeft(), value));;
}else if(value > root.getValue()) {
root.setRight(insertNode(root.getRight(), value));
}
return root;
}
Deletion
Deleting a node from BST. First, find the node to be deleted and then deal with it depending on it’s position in the tree. If it’s a leaf node, simply delete it. If it has only one child, then promote the child to its place. If it has both the children, then find the successor (details below) of the node, replace node’s value with its successor’s value and delete the successor.
/**
* Deleting a node from BST.
* @param root
* @param value
* @return
*/
public Node deleteNode(Node root, int value){
/* If root is null, return null */
if(null == root){
return null;
}
/* Traverse till the required key is hit */
if(value > root.getValue()){
root.setRight(deleteNode(root.getRight(), value));
}else if(value < root.getValue()){
root.setLeft(deleteNode(root.getLeft(), value));
}else {
/* case - Found the key */
// If it's leaf node, return null
if(null == root.getLeft() && null == root.getRight()){
return null;
}
// If it has one child, return that
else if(null == root.getLeft() || null == root.getRight()){
if(null == root.getLeft()){
return root.getRight();
}else{
return root.getLeft();
}
}
// If it has 2 children, find the successor node
else{
Node successor = findSuccessor(root, value);
root.setValue(successor.getValue());
successor.setValue(value);
root.setRight(deleteNode(root.getRight(), successor.getValue()));
}
}
return root;
}
Successor
Successor of a node is the node which carries the value that is next big to the given node in the BST.
/**
* Find successor.
* <p>
* Successor of a node is the node which carries the value that is next big to the given node in the BST.
* </p>
* @param root
* @param key
* @return
*/
public Node findSuccessor(Node root, int key){
/* If root is null, return null */
if(null == root){
return null;
}
Node successor = null;
/* If root has the intended key, then find successor */
if(key == root.getValue()){
/* Successor is the smallest node in the right tree of the given root */
successor = root.getRight();
while(null != successor.getLeft()){
successor = successor.getLeft();
}
return successor;
}
/* Traverse left */
successor = findSuccessor(root.getLeft(), key);
if(null != successor){
return successor;
}
/* Traverse right */
successor = findSuccessor(root.getRight(), key);
return successor;
}
Predecessor
Predecessor of a node is the node which carries the value that is next less to the given node in the BST.
/**
* Find Predecessor of the given node.
* <p>
* Predecessor of a node is the node which carries the value that is next less to the given node in the BST.
* </p>
* @param root
* @param key
* @return
*/
public Node findPredecessor(Node root, int key){
/* If root is null, return null */
if(null == root){
return null;
}
Node predecessor = null;
/* If root has the intended key, then find successor */
if(key == root.getValue()){
/* Predessor is the largest node in the left tree of the given root */
predecessor = root.getLeft();
while(null != predecessor && null != predecessor.getRight()){
predecessor = predecessor.getRight();
}
return predecessor;
}
/* Traverse left */
predecessor = findPredecessor(root.getLeft(), key);
if(null != predecessor){
return predecessor;
}
/* Traverse right */
predecessor = findPredecessor(root.getRight(), key);
return predecessor;
}
Minimum value
Find minimum value in a BST.
/**
* Find the minimum value node in a BST
* @param root
* @return
*/
public Node findMinValue(Node root){
/* If root's left is available, keep traversing till the leaf and that's the minimum */
if(null != root && null != root.getLeft()){
return findMinValue(root.getLeft());
}else {
return root;
}
}
Grab the source code from Github and try these out.