binary_tree icon indicating copy to clipboard operation
binary_tree copied to clipboard

BinaryTree.remove() removes more than one entry

Open Blimster opened this issue 1 month ago • 0 comments

When I create a binary tree like this:

final tree = BinaryTree<int>([
    15985,
    15977,
    16006,
    4508,
    15982,
    16000,
    16022,
    4500,
    15964,
    15978,
    15984,
    15999,
    16005,
    16019,
    16041,
    15980,
    15983,
    16040
  ]);

and then remove the entry 15977, the entry 15980 is also removed.

Before the call to remove(), the tree looks like this:

15985
  L:15977
    L:4508
      L:4500
      R:15964
    R:15982
      L:15978
        R:15980
      R:15984
        L:15983
  R:16006
    L:16000
      L:15999
      R:16005
    R:16022
      L:16019
      R:16041
        L:16040

and after the call like this:

15985
  L:15978
    L:4508
      L:4500
      R:15964
    R:15984
      L:15982
        R:15983
  R:16006
    L:16000
      L:15999
      R:16005
    R:16022
      L:16019
      R:16041
        L:16040

Here is the full code to reproduce the issue:

void main() {
  final tree = BinaryTree<int>([
    15985,
    15977,
    16006,
    4508,
    15982,
    16000,
    16022,
    4500,
    15964,
    15978,
    15984,
    15999,
    16005,
    16019,
    16041,
    15980,
    15983,
    16040
  ]);

  printTreeNode(tree.root);
  tree.remove(15977);
  printTreeNode(tree.root);

  print('length: ${tree.length}');
  print('entries: ${tree.toList()}');
}

void printTreeNode(TreeNode<int> node, {String prefix = '', int indent = 0}) {
  print(' ' * indent + prefix + node.data.toString());
  final left = node.left;
  if (left != null) {
    printTreeNode(left, prefix: 'L:', indent: indent + 2);
  }
  final right = node.right;
  if (right != null) {
    printTreeNode(right, prefix: 'R:', indent: indent + 2);
  }
}

Blimster avatar Jan 03 '25 16:01 Blimster