how to find the max object in binary search tree

Question

hi i build this code for BST: public class BinarySearchTreeCode {

private class BSTNode {
    public Object data;
    public BSTNode left;
    public BSTNode right;
    BSTNode(Object newdata) {
        data = newdata;
        left = null;
        right = null;
    }
    BSTNode(Object data, BSTNode left, BSTNode right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
    public String toString(){
        return "data: "+data+" ";
    }
}


// tree root
private BSTNode root;

public BinarySearchTreeCode(){
    root = null;

}
public BinarySearchTreeCode(BSTNode n){
    root = n;
}

public BinarySearchTreeCode(BinarySearchTreeCode bst){// copy constructor
    this.root = clone(bst.root);
}
BSTNode clone(final BSTNode source){
    if (source == null) return null;
    else
        return  new BSTNode(source.data, clone(source.left), clone(source.right));
}

// compare two objects (integer type)
private static int compare(Object o1, Object o2) {       
    int ans = 0;
    int n1 = (Integer)o1;
    int n2 = (Integer)o2;
    if(n1>n2) ans = 1;
    else if(n1<n2) ans = -1;
    return ans;
}

// insert element to the tree
public void insertRecurs(Object elem) {
    root = insertRecurs(root, elem);
}
BSTNode insertRecurs(BSTNode node, Object elem) {
    if (node == null) {

        return new BSTNode(elem);
    }
    if (compare(elem, node.data) < 0) {
        node.left = insertRecurs(node.left, elem);
        return node;
    }
    else{
        node.right = insertRecurs(node.right, elem);
        return node;
    }
}

// search for element elem
public boolean find(Object elem) {
    return find(root,elem);
}
boolean find(BSTNode tree, Object elem) {
    if (tree == null)
        return false;
    if (compare(elem, tree.data) == 0) 
        return true;
    if (compare(elem, tree.data) < 0)
        return find(tree.left, elem);
    else
        return find(tree.right, elem);
}

// print all tree nodes
public void print() {
    print(" ",root);
    System.out.println();
}
void print(String s,BSTNode tree) {//Inorder
    if (tree != null) {
        print(s+"L ,",tree.left);
        System.out.println(tree.data+" : "+s);
        print(s+"R ,",tree.right);
    }
}
///////////////////////////
public void remove(Object elem) {
    root = remove(root, elem);
}
public static BSTNode remove(BSTNode node, Object n){
    if(node != null){
        if(compare(n,node.data) > 0){
            node.right = remove(node.right,n);
        }
        else if(compare(n,node.data) < 0){
            node.left = remove(node.left,n);
        }
        else{//the node that should be deleted is found
            if(node.left == null && node.right == null){
                node = null;
            }
            else if(node.left != null && node.right == null){//the node has only one child (left)
                node = node.left;
            }
            else if(node.right != null && node.left == null){//the node has only one child (right)
                node = node.right;
            }
            else{//node "tree" has two children
                if(node.right.left == null){// his right node has only one child (right)
                    node.right.left = node.left;
                    node = node.right;
                }
                else{// remove the smallest element
                    BSTNode q, p = node.right;
                    while(p.left.left != null)
                        p = p.left;
                    q = p.left;
                    p.left = q.right;
                    node.data = q.data;
                }
            }
        }
    }
    return node;
}
public void insertLoop(Object elem) {
    BSTNode newNode = new BSTNode(elem);
    if (root == null){
        root = newNode;
    }
    else{
        BSTNode n = root;
        boolean flag = true;
        while (flag){
            if (compare(elem,n.data) > 0){
                if (n.right != null) n = n.right;
                else{
                    n.right = newNode;
                    flag = false;;
                }
            }
            else{
                if (n.left != null) n = n.left;
                else{
                    n.left = newNode;
                    flag = false;;
                }
            }
        }

    }
}
public boolean isEmpty(){
    return this.root == null;
}

//end of the code

the question is how i build a function that give the max object in the BNT like this

public Object maximum(){

}

any Suggestions?

thank for yours help.

Answer 1

The maximum object in a Binary Search tree is the rightmost node. You can get it as follows :

1) Start from root node

2) Check if node.right is empty

3) If yes then node is the maximum object. terminate the search.

4) if not then move to rightmost nde (node = node.right) and repeat step 2.

Sample Code :

public BSTNode  findMaxNode()
{
     Node temp = root;
     Node max = null;
     while(temp != null)
     {
        max = temp;
        temp = temp.right
     }

   return max;
}