diff -r f49f8a7060aa -r f4e00bb3f3b2 tests/test_tree.c
--- a/tests/test_tree.c	Sat Oct 05 14:42:14 2024 +0200
+++ b/tests/test_tree.c	Sat Oct 05 19:05:47 2024 +0200
@@ -1719,6 +1719,20 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+static void test_tree_remove_node_relink_mock(
+        void *node,
+        __attribute__((__unused__)) const void *oldp,
+        __attribute__((__unused__)) const void *newp
+) {
+    tree_node_file * n = node;
+    // this function fakes the relink logic in below test
+    if (strcmp(n->path, "/usr/share/") == 0) {
+        n->path = "/share/";
+    } else if (strcmp(n->path, "/usr/lib/") == 0) {
+        n->path = "/lib/";
+    }
+}
+
 CX_TEST(test_tree_high_add_find_remove_nodes) {
     CxTestingAllocator talloc;
     cx_testing_allocator_init(&talloc);
@@ -1765,20 +1779,41 @@
 
         tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
         share->path = "/usr/share/";
-        cxTreeAddChildNode(tree, cxTreeFind(tree, "/usr/"), share);
+        tree_node_file *usr = cxTreeFind(tree, "/usr/");
+        cxTreeAddChildNode(tree, usr, share);
         CX_TEST_ASSERT(tree->size == 8);
 
         cxTreeRemoveSubtree(tree, foo);
+        CX_TEST_ASSERT(tree->size == 6);
+        CX_TEST_ASSERT(foo->children == bar);
+        CX_TEST_ASSERT(foo->last_child == bar);
         CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/"));
         CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/"));
         CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/"));
-        CX_TEST_ASSERT(tree->size == 6);
+
+        CX_TEST_ASSERT(0 == cxTreeRemove(tree, usr, test_tree_remove_node_relink_mock));
+        CX_TEST_ASSERT(tree->size == 5);
+        CX_TEST_ASSERT(usr->parent == NULL);
+        CX_TEST_ASSERT(usr->children == NULL);
+        CX_TEST_ASSERT(usr->last_child == NULL);
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/"));
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/"));
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/"));
+        tree_node_file *relinked_share = cxTreeFind(tree, "/share/");
+        tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/");
+        CX_TEST_ASSERT(relinked_share != NULL);
+        CX_TEST_ASSERT(relinked_share->parent == tree->root);
+        CX_TEST_ASSERT(relinked_lib != NULL);
+        CX_TEST_ASSERT(relinked_lib->parent == tree->root);
+        CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/"));
+
 
         cxTreeDestroy(tree);
-        // we are not done yet, because we need to free the removed subtree
+        // we are not done yet, because we need to free the removed stuff
         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
 
-        // for this, we use a little trick and wrap the removed subtree
+        cxFree(alloc, usr);
+        // for the subtree, we use a little trick and wrap it in a new tree
         CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout);
         foo_tree->allocator = alloc;
         foo_tree->advanced_destructor = (cx_destructor_func2 ) cxFree;
@@ -1811,6 +1846,9 @@
         };
         cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
         void *root = tree->root;
+        CX_TEST_ASSERT(0 != cxTreeRemove(tree, root, NULL));
+        CX_TEST_ASSERT(tree->root == root);
+        CX_TEST_ASSERT(tree->size == 6);
         cxTreeRemoveSubtree(tree, root);
         CX_TEST_ASSERT(tree->size == 0);
         CX_TEST_ASSERT(tree->root == NULL);