binary search tree - Getting an object from a recursive deletion Java -

binary search tree - Getting an object from a recursive deletion Java -

i have binary search tree contains nodes. each node contains key value , info value, , nodes sorted key. trying write method remove object bst provided key. here code:

public object remove(comparable thekey) { homecoming remove(thekey, rootptr).data; } public node remove(comparable thekey, node node) { object o; if(node == null) homecoming node; if(thekey.compareto(node.key) < 0) { // go left subtree node.leftchild = remove(thekey, node.leftchild); }else if(thekey.compareto(node.key) > 0) { //go right subtree node.rightchild = remove(thekey, node.rightchild); }else if(thekey.compareto(node.key) == 0) { if(node.leftchild != null && node.rightchild != null){ node foundnode = findmin(node.rightchild); node.key = foundnode.key; node.data = foundnode.data; node.rightchild = remove(node.key, node.rightchild); }else{ if(node.leftchild != null){ node = node.leftchild; }else{ node = node.rightchild; } } } numnodes--; homecoming node; }

i homecoming info value associated deleted node. issue have that: in public object remove() method, wouldn't returned value info value of root node? believe occur because final returned phone call sec method reference rootptr (root pointer). if case, how can save info deleted node?

the simplest solution seems to add together output parameter hands result:

public object remove(comparable thekey) { object[] result = new object[1]; rootptr = remove(thekey, rootptr, result); // prepare deletion one-node tree homecoming result[0]; } public node remove(comparable thekey, node node, object[] result) { if(node == null) { homecoming node; } int diff = thekey.compareto(node.key); if (diff < 0) { node.leftchild = remove(thekey, node.leftchild, result); } else if (diff > 0) { node.rightchild = remove(thekey, node.rightchild, result); } else { result[0] = node.key; if (node.rightchild == null) { node = node.leftchild; } else if (node.leftchild == null) { node = node.rightchild; } else { node foundnode = findmin(node.rightchild); node.key = foundnode.key; node.data = foundnode.data; node.rightchild = remove(node.key, node.rightchild, new object[1]); } numnodes--; } homecoming node; }

returning found node doesn't work without important changes because homecoming parameter used replace nodes needed, , in case found node has 2 children, you'd need create re-create or insert new node. handling case root node gets removed issue, too.

p.s. assuming not "trick question" , can't homecoming thekey -- has equal found key after :)

java binary-search-tree