Description
At master2fdcde75a497bdedcd5385bda224b4fb80ea3d15, KDTree.delete can return normally without removing a non-root point. Replacement deletion can also leave duplicate/unreachable points when the target has descendants.
The recursive delete method descends left when the current coordinate is smaller than the target coordinate; insert/search descend right in that case. In the only-left-subtree case, replacing a point with the minimum of that subtree and retaining the rest on the left also violates the split ordering.
Reproduction
A test in package com.thealgorithms.datastructures.trees can insert the points (20,20), (10,10), (30,30) into new KDTree(2), then call delete(new KDTree.Point(new int[] {10,10})).
Expected: two stored points remain and search for (10,10) is empty.
Actual: all three stored points remain; deletion silently follows the opposite child.
The same regression suite also exercises a root with only a left subtree, nested replacement successors, both-side non-root targets, and complete deletion sequences on inserted/bulk-built 1D/2D/3D trees. Coordinates are distinct on each axis; this report concerns the deletion algorithm, not duplicate-axis construction or nearest-neighbor arithmetic.
Native evidence
Native Maven/JUnit reproduction uses official Temurin21 and this repository's actual Maven configuration. Original KDTree production blob5190e82f74ef4aac7079f4df13329e38881473d0 is unchanged and verified before execution. Command:
mvn --batch-mode -Dtest=KDTreeTest,KDTreeDeletionTest test
All three existing KDTree tests pass. All six focused deletion regressions fail with assertions, zero errors: expected remaining counts2/8/3/4/1/14 versus actual3/9/4/5/2/15. Maven exits1 because of those genuine failures. The regression source and complete native reports are available in the linked run and its artifact.
Tests were developed with OpenAI Codex assistance. I am preparing a focused fix preserving the existing public API and unrelated algorithm behavior.
Description
At master2fdcde75a497bdedcd5385bda224b4fb80ea3d15, KDTree.delete can return normally without removing a non-root point. Replacement deletion can also leave duplicate/unreachable points when the target has descendants.
The recursive delete method descends left when the current coordinate is smaller than the target coordinate; insert/search descend right in that case. In the only-left-subtree case, replacing a point with the minimum of that subtree and retaining the rest on the left also violates the split ordering.
Reproduction
A test in package com.thealgorithms.datastructures.trees can insert the points (20,20), (10,10), (30,30) into new KDTree(2), then call delete(new KDTree.Point(new int[] {10,10})).
Expected: two stored points remain and search for (10,10) is empty.
Actual: all three stored points remain; deletion silently follows the opposite child.
The same regression suite also exercises a root with only a left subtree, nested replacement successors, both-side non-root targets, and complete deletion sequences on inserted/bulk-built 1D/2D/3D trees. Coordinates are distinct on each axis; this report concerns the deletion algorithm, not duplicate-axis construction or nearest-neighbor arithmetic.
Native evidence
Native Maven/JUnit reproduction uses official Temurin21 and this repository's actual Maven configuration. Original KDTree production blob5190e82f74ef4aac7079f4df13329e38881473d0 is unchanged and verified before execution. Command:
All three existing KDTree tests pass. All six focused deletion regressions fail with assertions, zero errors: expected remaining counts2/8/3/4/1/14 versus actual3/9/4/5/2/15. Maven exits1 because of those genuine failures. The regression source and complete native reports are available in the linked run and its artifact.
Tests were developed with OpenAI Codex assistance. I am preparing a focused fix preserving the existing public API and unrelated algorithm behavior.