Binary Search Tree is a data structure in which the given tree is structured in such a way that the left child node is always less than the parent node and the parent node is always less than the right child node.
In this tutorial we will see how to find the minimum element and also how to delete the node with the minimum value from a BST.
First we create a node with data and left and right pointers which will help us store information about any given node's two children node.
public class Node {
public int element; // The data in the node
public Node left; // Left child
public Node right; // Right child
public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}
In order to find the minimum element in a BST, we have to understand that the minimum always resides on the most left side of the tree. That means we keep traversing to the left side of the tree until it is null.
To remove the minimum, we need to keep track of two references (one is the left hand side node on each level of the tree and one is the parent of this node).
As soon as we reach the last node of the left most side of the tree, then we will check if that node has any right children.
If so we should let the parent of the left most node to adapt them as its own children.
If no children, then we can simply assign the parent left child as null.
public class MyBST
{
/** The tree root. */
private Node root;
public int findMin() {
return findMin(root).element;
}
private Node findMin(Node start){
Node min = start;
if (min.left != null)
return findMin(min.left);
else
return min;
}
public object removeMin() {
if (root == null)
return null;
return removeMin(root, root);
}
private int removeMin(Node n, Node curparent) {
if (n.left != null) {
return removeMin(n.left, n);
}
else {
if (n.right != null)
curparent.left = n.right;
else
curparent.left = null;
return n.element;
}
}
}