java - Binary Search Tree In Order Predecessor not removing node -

java - Binary Search Tree In Order Predecessor not removing node -

i've been trying bst work, issue persists node succeeding removed node never removed.

[ <p, 1>, <c, 26>, <u, 3>, <b, 293>, <h, 1>, <r, 12>, <v, 42>, null, null, null, <k, 465>, <q, 465>, <s, 42>, null, null, null, null, null, null, null, null, null, <l, 465>, null, null, null, <t, 465>, ] [ <p, 1>, <c, 26>, **<t, 465>**, <b, 293>, <h, 1>, <r, 12>, <v, 42>, null, null, null, <k, 465>, <q, 465>, <s, 42>, null, null, null, null, null, null, null, null, null, <l, 465>, null, null, null, **<t, 465>**, ] bst : inorder successor , predecessor binarysearchtree predecessor algorithm http://codereview.stackexchange.com/questions/35219/in-order-predecessor-bst-review

and looking @ these other implementations , adapting proper properties of tree:

http://algs4.cs.princeton.edu/32bst/bst.java.html http://cslibrary.stanford.edu/110/binarytrees.html https://www.cs.cmu.edu/~adamchik/15-121/lectures/trees/code/bst.java

public class binarysearchtree<key extends comparable<key>, value extends comparable<value>>{ class node extends keyvaluepair<key, value> { private int position = -1; private node leftchild = null; private node rightchild = null; private keyvaluepair<key, value> pair = new keyvaluepair<key, value>(); // getters , setters public node findmax() { node newcur = this; while (newcur.getrightchild() != null) { newcur = newcur.getrightchild(); } homecoming newcur; } } private int pos = -1; // helps maintain track of node in tree private int bstsize = 0; private int largestpos = -1; protected node root = null; private node findkey(key keytomatch, node current) { if (current == null || current.getkey() == keytomatch) { homecoming current; } else if (keytomatch.compareto(current.getkey()) < 0) { homecoming findkey(keytomatch, current.getleftchild()); } else { homecoming findkey(keytomatch, current.getrightchild()); } } private node put(node node, node temp) { if (node == null) { node = temp; } else if (temp.getkey().compareto(node.getkey()) < 0) { node.setleftchild(put(node.getleftchild(), temp)); } else if (temp.getkey().compareto(node.getkey()) > 0) { node.setrightchild(put(node.getrightchild(), temp)); } homecoming node; } @override public value put(key key, value value) { if (key == null || value == null) { homecoming null; } node temp = new node(); temp.setkey(key); temp.setvalue(value); node oldnode = null; value oldval = null; if (root == null) { root = temp; } else { oldnode = findkey(key, root); if (oldnode != null) { // means there key match oldval = oldnode.getvalue(); oldnode.setvalue(value); } else { put(root, temp); } } homecoming oldval; } private node remove(node current, key key) { node temp = new node(); if(current == null) { homecoming null; } else if(key.compareto(current.getkey()) < 0) { remove(current.getleftchild(), key); } else if(key.compareto(current.getkey()) > 0) { remove(current.getrightchild(), key); } else { if (current.getrightchild() == null) homecoming current.getleftchild(); else if(current.getleftchild() == null) homecoming current.getrightchild(); current.setkey(current.getleftchild().findmax().getkey()); current.setvalue(current.getleftchild().findmax().getvalue()); current.setleftchild(remove(current.getleftchild(), current.getkey())); } homecoming current; } @override public value remove(key key) { if (key == null || root == null) { homecoming null; } node current = findkey(key, root); value val = null; if(current == null) { homecoming val; } else { val = current.getvalue(); remove(root, key); } homecoming val; } public keyvaluepair<key, value>[] breadthfirsttraversal() { @suppresswarnings("unchecked") keyvaluepair<key, value>[] bftarray = new keyvaluepair[largestpos]; keyvaluepair<key, value> nodeval = null; if (!isempty()) { (int = 1; < bftarray.length + 1; i++) { keypos.reset(); if (positionfound(i)) { nodeval = findposkey(root, i); bftarray[i - 1] = nodeval; } else { bftarray[i - 1] = null; } } } homecoming bftarray; } }

java binary-search-tree