Binary Tree Delete Implementation

Question

I'm attempting to implement a simple binary tree in Dart. My insert and search seem to work just fine, but my delete/remove does not.

void delete(int targetData) {
BinarySearchTreeNode? target = find(targetData);
if (target == null) {
  return;
}
if (target.left == null && target.right == null) {
  target = null;
} else {
  //This means the target has at least one child.
  //Let's take care of the one child case first.
  if (target.left == null) {
    target = target.right;
  } else if (target.right == null) {
    target = target.left;
  } else {
    //This means both children are present.
    BinarySearchTreeNode? current = target.right;
    if (current!.left == null) {
      BinarySearchTreeNode newTarget =
          BinarySearchTreeNode(current.nodeData);
      newTarget.left = target.left;
      newTarget.right = target.right;
      target = newTarget;
    } else {
      BinarySearchTreeNode? previous;
      while (current != null) {
        previous = current;
        current = current.left;
      }
      BinarySearchTreeNode newTarget =
          BinarySearchTreeNode(previous!.nodeData);
      newTarget.left = target.left;
      newTarget.right = target.right;
      target = newTarget;
      delete(previous.nodeData);
    }
  }
}

}

After I run delete on an existing node, the tree seems to remain the same. I've also tried using the same code from my find method instead of passing the target. The code shows no runtime errors. Here's my full code in DartPad in case anyone believes the problem is outside of the method.

Answer 1

The problem is here:

  print('Deleting $targetData');
  if (target.left == null && target.right == null) {
    //print('    $targetData has no children. Setting node to null');
    target = null;

target is a local variable, so setting it to null does nothing. In particular, it doesn't modify the tree.

If you think about the process of: insert(10) followed immediately by delete(10) you want to end up with an empty tree. The only way you'll achieve that is if you somehow write _root = null;. This would mean you need to compare target with _root and take special action when removing the last node (as you do in the first few steps of your example).

To repeat, this code does not empty the tree:

var target = _root;
target = null; // this does *not* set _root to null

In general, as you walk the tree looking for what you want to delete, you'll have to keep another local variable pointing to where you came from (i.e. the parent). Then when you want to delete one of its children, you still have a reference to the parent and can say, for example, parent.left = null;

Again:

var target = someNode.left;
target = null; // this does *not* set someNode.left to null

vs

var parent = someNode;
var target = parent.left;
parent.left = null; // this *does* set someNode.left to null