data structures - Find Ancestor method for binary search tree is not working -

data structures - Find Ancestor method for binary search tree is not working -

i had written method finding node's parent in c# (c-sharp) code not working correctly. exceptions: system.nullreferenceexception thrown when seek delete node who's parent null.

public treenode findparent(int value, ref treenode parent) { treenode currentnode = root; if (currentnode == null) { homecoming null; } while (currentnode.value != value) { if (value < currentnode.value) { parent = currentnode; currentnode = currentnode.leftchild; } if (value > currentnode.value) { parent = currentnode; currentnode = currentnode.rightchild; } } homecoming currentnode; } public void delete(int value) { treenode parent = null; treenode nodetodelete = findparent(value, ref parent); if (nodetodelete == null) { throw new exception("unable delete node: " + value.tostring()); } //case 1: nod has 0 children. if (nodetodelete.leftchild == null && nodetodelete.rightchild == null) { if (parent.leftchild == nodetodelete) { parent.leftchild = null; } if (parent.rightchild == nodetodelete) { parent.rightchild = null; } count--; return; } //case 2: nod has 1 left || 1 right barn if (nodetodelete.leftchild == null && nodetodelete.rightchild != null) { nodetodelete.rightchild = parent.rightchild; nodetodelete = null; count--; return; } if (nodetodelete.leftchild != null && nodetodelete.rightchild == null) { nodetodelete.leftchild = parent.leftchild; nodetodelete = null; count--; return; } //case 3: nod has 2 children if (nodetodelete.rightchild != null && nodetodelete.leftchild != null) { treenode successor = leftmostnodeonright(nodetodelete, ref parent); treenode temp = new treenode(successor.value); if (parent.leftchild == successor) { parent.leftchild = successor.rightchild; } else { parent.rightchild = successor.rightchild; nodetodelete.value = temp.value; } count--; return; } }

since using recursion , don't need parent node delete node in binary search tree, here delete method pass in int , root

private binarytreenode remove (int value, treenode t){ if(t==null) homecoming t; // not found; nil if(value < t.value){ t.left = remove(x,y,t.left); } else if (value > t.value){ t.right = remove(x,y,t.right); } else if( t.left!=null && t.right != null) // 2 children { t.info = findmin(t.right).info; remove(t.info.getlastname(),y,t.right); } else{ // 1 kid if (t.left != null) { t = t.left; } else{ t = t.right; } } homecoming t; }

edit-----------findmin (find minimum node in binary search tree)

private binarytreenode findmin ( binarytreenode t){ // recursive if(t == null) homecoming null; else if (t.left == null) homecoming t; homecoming findmin(t.left); }

so take min value right subtree, , create parent of t.info. follow these diagrams. deleting node 25 2 children.

data-structures parent binary-search-tree nullreferenceexception