Bug in `BinarySearchTree.from()`: Removing Elements from Copy Corrupts Original Tree

[jiangshengdev]

trafficstars

Describe the bug

When creating a copy of a BinarySearchTree using the BinarySearchTree.from() method, removing an element from the copied tree inadvertently affects the original tree. Specifically, the original tree either loses elements or its internal structure becomes inconsistent after modifications to the copy.

Steps to Reproduce

1. Create a BinarySearchTree with the values [3, 10, 13, 4, 6, 7, 1, 14].
2. Use BinarySearchTree.from(original) to create a copy of the original tree.
3. Remove the value 7 from the copied tree using copy.remove(7).
4. Attempt to find the value 7 in the original tree using original.find(7).

Expected behavior

After removing the value 7 from the copied tree, the original tree should remain unaffected. The value 7 should still be present in the original tree, and its size and internal structure should remain consistent.

Environment

• OS: MacOS 15.1.1
• deno version: 2.0.3
• std version:

  {
    "name": "@std/data-structures",
    "version": "1.0.5"
  }
  

Test Case

Deno.test("BinarySearchTree.from() bug demo - removing in copy corrupts original", () => {
  // 1. Build the original tree
  const values = [3, 10, 13, 4, 6, 7, 1, 14];
  const original = BinarySearchTree.from(values);
  // original should have 8 elements and include 7

  // 2. Create a copy without passing compare/map
  const copy = BinarySearchTree.from(original);
  // copy and original should be independent trees

  // 3. Remove value 7 from the copy
  const removedInCopy = 7;
  const removeResult = copy.remove(removedInCopy);
  // If all is well, removing 7 from copy should not affect original

  // 4. Original tree should still find 7
  const stillInOriginal = original.find(removedInCopy);

  // Assertion: original should still contain 7
  assertStrictEquals(stillInOriginal !== null, true, `Expected original.find(${removedInCopy}) to not be null, but got null.`);

  // Additionally, check if removeResult is true
  assertStrictEquals(removeResult, true, `Expected copy.remove(${removedInCopy}) to return true, but got false.`);
});