Thread: Binary Search Tree

hi, I'm new to this forum, so first of all I think I should introduce myself, hi I'm lex.... So basically the other day I was given the following assignment: 'Given the following interface (BST) and the following class (BSTNode), create your very own Binary Search Tree implementation'.

public final class BSTNode {
    private int key;
    private String value;
    private BSTNode left;
    private BSTNode right;
 
    public BSTNode() {
    }
 
    public int getKey() {
        return key;
    }
 
    public void setKey(int key) {
        this.key = key;
    }
 
    public BSTNode getLeft() {
        return left;
    }
 
    public void setLeft(BSTNode left) {
        this.left = left;
    }
 
    public BSTNode getRight() {
        return right;
    }
 
    public void setRight(BSTNode right) {
        this.right = right;
    }
 
    public String getValue() {
        return value;
    }
 
    public void setValue(String value) {
        this.value = value;
    }
 
    @Override
    public String toString() {
        return "<" + key + "=" + value + ">";
    }
}
 
public class BSTImpl implements BST{
 
    private BSTNode root;
 
    public  BSTImpl(){
        root=null;
    }
 
    private String findRic(int key, BSTNode node){
        if(node==null) return null;
        if(node.getKey()==key) return node.getValue();
        if(key<node.getKey()) return findRic(key, node.getLeft());
        else return findRic(key, node.getRight());
    }
 
    public String find(int key) {
       return findRic(key, root);
    }
 
    private void findAllRic(int key, BSTNode node, List list){
        if(node==null) return;
        if(node.getKey()==key){
            list.add(node.getValue());
            findAllRic(key,node.getRight(),list);
        }
        if(key<node.getKey()) findAllRic(key, node.getLeft(), list);
        else findAllRic(key, node.getRight(), list);
    }
 
    public List<String> findAll(int key) {
        List result = new LinkedList();
        findAllRic(key,root,result);
        return result;
    }
 
    private void insertIfAintEmpty(int key, String value, BSTNode node){
        if(key>=node.getKey()){
            if(node.getRight()==null){
                BSTNode child = new BSTNode();
                child.setKey(key);
                child.setValue(value);
                node.setRight(child);
            }
            else insertIfAintEmpty(key,value,node.getRight());
        }
        else{
            if(node.getLeft()==null){
                BSTNode child = new BSTNode();
                child.setKey(key);
                child.setValue(value);
                node.setLeft(child);
            }
            else insertIfAintEmpty(key,value,node.getLeft());
        }
    }
 
    public void insert(int key, String value) {
        if(root==null){
            BSTNode node=new BSTNode();
            node.setKey(key);
            node.setValue(value);
            root=node;
        }
        else insertIfAintEmpty(key,value,root);
    }
 
    public boolean isEmpty() {
        return root==null;
    }
 
    public BSTNode root() {
        return root;
    }
 
    private int sizeRic(BSTNode node){
        if(node==null) return 0;
        else return 1 + sizeRic(node.getLeft()) + sizeRic(node.getRight());
    }
 
    public int size() {
        return sizeRic(root);
    }
 
    private void removeIt(int key, BSTNode node) {
        BSTNode temp=root;
        while(temp.getKey()>key){
            temp=node.getLeft();
        }
        root=temp;
    }
 
    private int min(int key, BSTNode node){
        while(node.getLeft()!=null){
            node=node.getLeft();
        }
        return node.getKey();
    }
 
    private void removeRic(int key, BSTNode node){
        if(node==null) return;
        if(node.getLeft().getKey()>key) removeRic(key, node.getLeft());
        if(node.getRight().getKey()>key && node.getRight()!=null){
           node.setRight(node.getRight().getLeft());
        }
        if(node.getRight().getKey()<key) removeRic(key, node.getRight());
}
 
    public void removeHigh(int k) {
        removeRic(key,root);
    }
 
    private int max(int key, BSTNode node) {
         while(node.getRight()!=null){
            node=node.getRight();
        }
        return node.getKey();
    }
 
    public void print(){
        printRic(root);
    }
 
    private void printRic(BSTNode node){
        if(node.getLeft()!=null) printRic(node.getLeft());
        System.out.println(node);
        if(node.getRight()!=null) printRic(node.getRight());
    }
 
}
 
import java.util.*;
 
public interface BST{
 
    public String find(int key);
 
    public List<String> findAll(int key);
 
    public void insert(int key, String value);
 
    public boolean isEmpty();
 
    public BSTNode root();
 
    public int size();
 
    public void removeHigh(int k);
}

What I am really having a problem with is removeHigh which is supposed to remove any nodes whose key's greater than k, only thing is I've always been bad at deletions especially when it comes to trees... any help would be immensely appreciated

Originally Posted by KevinWorkman

What are you having trouble with? What did you try? What worked, what didn't work? How didn't it work? Be specific. Saying "I'm bad at this" doesn't really give us much to go off.

It all goes smooth except for removeHigh... which doesn't seem to do anything...

here's the tester I used

 public static void main(String[] x){
        BSTImpl dic = new BSTImpl();
        dic.insert(3, "3");
        dic.insert(2, "2");
        dic.insert(5, "5");
        dic.insert(4, "4");
        dic.insert(6, "6");
        dic.insert(1, "1");
        dic.removeHigh(1);
        dic.print();
        System.out.println(dic.size());

what it does is it removes 5 and 6