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. You can visualize a tree like an actual inverted tree as shown in the above picture where the root is on the top and branches are below it.
In this tutorial we will see how to find an element with the maximum value and also how to delete it 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 maximum element in a BST, we have to understand that the maximum always resides on the most right side of the tree. That means we keep traversing to the right side of the tree until it is null.
To remove the maximum , we need to keep track of two references (one is the right 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 right most side of the tree, then we will check if that node has any left children.
If so we should let the parent of the this right most node to adapt them as its own children.
If no children, then we can simply assign the parent of this right most node right child as null.
public class MyBST
{
/** The tree root. */
private Node root;
public int findMax() {
return findMax(root).element;
}
private Node findMax(Node start) {
Node max = start;
if (max.right != null)
return findMax(max.right);
else
return max;
}
public object removeMax() {
if (root == null)
return null;
return removeMax(root, root);
}
private int removeMax(Node n, Node curparent) {
if (n.left != null) {
return removeMax(n.left, n);
}
else {
if (n.right != null)
curparent.right = n.left;
else
curparent.right = null;
return n.element;
}
}
}