diff -r a5b7cf49dea7 -r 7d41291b3095 tests/test_tree.c
--- a/tests/test_tree.c	Wed Dec 31 13:39:55 2025 +0100
+++ b/tests/test_tree.c	Wed Dec 31 14:58:40 2025 +0100
@@ -443,6 +443,14 @@
     int r;
     tree_node *n;
     CX_TEST_DO {
+        // special case: search an empty tree
+        n = (void*)0x1337;
+        r = cx_tree_search(NULL, 0, &s, test_tree_search_function,
+                               (void **) &n, tree_children(tree_node));
+        CX_TEST_ASSERT(r < 0);
+        CX_TEST_ASSERT(n == NULL);
+
+        // search for the test data (exact matches)
         for (unsigned i = 0 ; i <= 10 ; i++) {
             s = testdata[i];
             r = cx_tree_search(&root, 0, &s, test_tree_search_function,
@@ -1049,6 +1057,26 @@
     }
 }
 
+CX_TEST(test_tree_visitor_create_for_empty_tree) {
+    CX_TEST_DO {
+        CxTreeIterator iter = cx_tree_visitor(NULL, tree_children(tree_node));
+        CX_TEST_ASSERT(!iter.visit_on_exit);
+        CX_TEST_ASSERT(!iter.exiting);
+        CX_TEST_ASSERT(iter.counter == 0);
+        CX_TEST_ASSERT(iter.node == NULL);
+        CX_TEST_ASSERT(!iter.base.allow_remove);
+        CX_TEST_ASSERT(!iter.base.remove);
+        CX_TEST_ASSERT(iter.queue_next == NULL);
+        CX_TEST_ASSERT(iter.queue_last == 0);
+        CX_TEST_ASSERT(iter.depth == 0);
+        CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
+        CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
+        CX_TEST_ASSERT(!cxIteratorValid(iter));
+        // disposing this iterator should also be harmless
+        cxTreeIteratorDispose(&iter);
+    }
+}
+
 CX_TEST(test_tree_visitor_no_children) {
     tree_node root = {0};
 
@@ -1373,6 +1401,80 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+CX_TEST(test_tree_high_create_root) {
+    CxTestingAllocator talloc;
+    cx_testing_allocator_init(&talloc);
+    CX_TEST_DO {
+        CxTree *tree = cxTreeCreate(
+                &talloc.base,
+                sizeof(tree_node_file),
+                CX_STORE_POINTERS,
+                NULL, -1,
+                cx_tree_node_layout(tree_node_file)
+        );
+
+        CX_TEST_ASSERT(tree->root == NULL);
+        // create root without data
+        tree_node_file *root = cxTreeCreateRoot(tree);
+        CX_TEST_ASSERT(root != NULL);
+        CX_TEST_ASSERT(root == tree->root);
+        // re-create same root (does nothing)
+        tree_node_file *root2 = cxTreeCreateRoot(tree);
+        CX_TEST_ASSERT(root2 == root);
+
+        // next test
+        cxTreeClear(tree);
+
+        // try to create with data, but loc_data is not known
+        root = cxTreeCreateRootData(tree, "/");
+        CX_TEST_ASSERT(root == NULL);
+
+        // set the loc_data
+        tree->loc_data = offsetof(tree_node_file, path);
+        root = cxTreeCreateRootData(tree, "/");
+        CX_TEST_ASSERT(root != NULL);
+        CX_TEST_ASSERT(strcmp(root->path, "/") == 0);
+
+        cxTreeFree(tree);
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+}
+
+CX_TEST(test_tree_high_set_root) {
+    CxTestingAllocator talloc;
+    cx_testing_allocator_init(&talloc);
+    CX_TEST_DO {
+        CxTree *tree = cxTreeCreate(
+                &talloc.base,
+                sizeof(tree_node_file),
+                CX_STORE_POINTERS,
+                NULL, -1,
+                cx_tree_node_layout(tree_node_file)
+        );
+
+        CX_TEST_ASSERT(tree->root == NULL);
+
+        tree_node_file *root = cxTreeCreateRoot(tree);
+        CX_TEST_ASSERT(root != NULL);
+        CX_TEST_ASSERT(root == tree->root);
+
+        // create a different root externally
+        tree_node_file *root2 = cxZalloc(&talloc.base, sizeof(tree_node_file));
+
+        // replace the root
+        tree_node_file *old = cxTreeSetRoot(tree, root2);
+        CX_TEST_ASSERT(old == root);
+
+        // free the tree, check that there is memory leaking
+        cxTreeFree(tree);
+        CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
+
+        // free the old root, check that memory is fine
+        cxFree(&talloc.base, old);
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+}
+
 CX_TEST(test_tree_high_tree_depth) {
     tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
     cx_tree_add(&root, &child1, tree_node_layout);
@@ -1618,6 +1720,123 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+CX_TEST(test_tree_high_add_find_without_loc_data) {
+    CxTestingAllocator talloc;
+    cx_testing_allocator_init(&talloc);
+    CxAllocator *alloc = &talloc.base;
+    CX_TEST_DO {
+        CxTree *tree = cxTreeCreate(alloc,
+            sizeof(tree_node_file),
+            CX_STORE_POINTERS,
+            NULL, offsetof(tree_node_file, path),
+            cx_tree_node_layout(tree_node_file)
+        );
+        cxSetCompareFunc(tree, strcmp);
+        tree_node_file *root = cxTreeCreateRootData(tree, "/");
+        tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+        tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+        cxTreeAddData(tree, foo, "/home/foo/bar/");
+        tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+        cxTreeAddData(tree, usr, "/usr/lib/");
+
+        void *found = cxTreeFind(tree, "/home/foo/", true);
+        CX_TEST_ASSERT(found == foo);
+
+        // now remove the loc_data
+        tree->loc_data = -1;
+        found = cxTreeFind(tree, "/home/foo/", true);
+        CX_TEST_ASSERT(found == NULL);
+
+        CX_TEST_ASSERT(NULL == cxTreeAddData(tree, root, "/usr/local/"));
+
+        cxTreeFree(tree);
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+    cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_high_find_max_depth) {
+    CxTree *tree = cxTreeCreate(NULL,
+        sizeof(tree_node_file),
+        CX_STORE_POINTERS,
+        NULL, offsetof(tree_node_file, path),
+        cx_tree_node_layout(tree_node_file)
+    );
+    cxSetCompareFunc(tree, strcmp);
+    tree_node_file *root = cxTreeCreateRootData(tree, "/");
+    tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+    tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+    tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/");
+    tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+    cxTreeAddData(tree, usr, "/usr/lib/");
+    CX_TEST_DO {
+        CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 4, true));
+        CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 3, true));
+        CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 3, true));
+        CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 2, true));
+    }
+    cxTreeFree(tree);
+}
+
+CX_TEST(test_tree_high_find_fast) {
+    CxTree *tree = cxTreeCreate(NULL,
+        sizeof(tree_node_file),
+        CX_STORE_POINTERS,
+        NULL, offsetof(tree_node_file, path),
+        cx_tree_node_layout(tree_node_file)
+    );
+    cxSetCompareFunc(tree, strcmp);
+    tree_node_file *root = cxTreeCreateRootData(tree, "/");
+    tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+    tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+    tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/");
+    tree_node_file *baz = cxTreeAddData(tree, home, "/home/baz/");
+    tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+    tree_node_file *lib = cxTreeAddData(tree, usr, "/usr/lib/");
+    CX_TEST_DO {
+        // test that loc_data not needed for FindFast!
+        tree->loc_data = -1;
+
+        // find from root
+        CX_TEST_ASSERT(root == cxTreeFindFast(tree, "/",
+            tree_node_file_search_func));
+        CX_TEST_ASSERT(home == cxTreeFindFast(tree, "/home/",
+            tree_node_file_search_func));
+        CX_TEST_ASSERT(foo == cxTreeFindFast(tree, "/home/foo/",
+            tree_node_file_search_func));
+        CX_TEST_ASSERT(bar == cxTreeFindFast(tree, "/home/foo/bar/",
+            tree_node_file_search_func));
+        CX_TEST_ASSERT(usr == cxTreeFindFast(tree, "/usr/",
+            tree_node_file_search_func));
+        CX_TEST_ASSERT(lib == cxTreeFindFast(tree, "/usr/lib/",
+            tree_node_file_search_func));
+
+        // find from correct subtree
+        CX_TEST_ASSERT(foo == cxTreeFindFastInSubtree(tree, "/home/foo/",
+            tree_node_file_search_func, home, 0));
+        CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/",
+            tree_node_file_search_func, home, 0));
+        CX_TEST_ASSERT(lib == cxTreeFindFastInSubtree(tree, "/usr/lib/",
+            tree_node_file_search_func, usr, 0));
+
+        // find in wrong subtree
+        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/",
+            tree_node_file_search_func, usr, 0));
+        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/",
+            tree_node_file_search_func, baz, 0));
+        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/usr/lib/",
+            tree_node_file_search_func, home, 0));
+
+        // some tests with max depth
+        // -------------------------
+        CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 4));
+        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 3));
+        CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 3));
+        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 2));
+    }
+    cxTreeFree(tree);
+}
+
 CX_TEST(test_tree_high_remove_or_destroy_root) {
     CxTestingAllocator talloc;
     cx_testing_allocator_init(&talloc);
@@ -1733,6 +1952,44 @@
     cxTreeFree(tree);
 }
 
+CX_TEST(test_tree_high_iterator_large_depth) {
+    CxTree *tree = cxTreeCreate(NULL,
+            sizeof(tree_node),
+            sizeof(int),
+            NULL, offsetof(tree_node, data),
+            tree_node_layout
+    );
+    int c = 0;
+    tree_node *root = cxTreeCreateRootData(tree, &c);
+    unsigned depths[6] = {10, 20, 15, 30, 25, 5};
+    for (unsigned b = 0 ; b < 3 ; b++) {
+        c++;
+        tree_node *branch = cxTreeAddData(tree, root, &c);
+        tree_node *p = branch;
+        for (unsigned d = 0; d < depths[b*2+0] ; d++) {
+            c++;
+            p = cxTreeAddData(tree, p, &c);
+        }
+        p = branch;
+        for (unsigned d = 0; d < depths[b*2+1] ; d++) {
+            c++;
+            p = cxTreeAddData(tree, p, &c);
+        }
+    }
+    CX_TEST_DO {
+        CX_TEST_ASSERT(cxTreeSize(tree) == 109);
+        CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root) == 109);
+        CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children) == 1+depths[0]+depths[1]);
+        CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next) == 1+depths[2]+depths[3]);
+        CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next->next) == 1+depths[4]+depths[5]);
+        CxTreeIterator iter = cxTreeIterate(tree, false);
+        cx_foreach(tree_node*, n, iter) {
+            CX_TEST_ASSERT((size_t)n->data == iter.counter - 1);
+        }
+    }
+    cxTreeFree(tree);
+}
+
 CX_TEST(test_tree_high_visitor) {
     CxTree *tree = cxTreeCreate(NULL,
             sizeof(tree_node_file),
@@ -1798,6 +2055,7 @@
     cx_test_register(suite, test_tree_iterator_free_nodes);
     cx_test_register(suite, test_tree_visitor_create_and_dispose);
     cx_test_register(suite, test_tree_visitor);
+    cx_test_register(suite, test_tree_visitor_create_for_empty_tree);
     cx_test_register(suite, test_tree_visitor_no_children);
     cx_test_register(suite, test_tree_visitor_no_branching);
     cx_test_register(suite, test_tree_visitor_subtree);
@@ -1812,13 +2070,19 @@
     CxTestSuite *suite = cx_test_suite_new("tree (high level)");
 
     cx_test_register(suite, test_tree_high_create);
+    cx_test_register(suite, test_tree_high_create_root);
+    cx_test_register(suite, test_tree_high_set_root);
     cx_test_register(suite, test_tree_high_tree_depth);
     cx_test_register(suite, test_tree_high_set_parent);
     cx_test_register(suite, test_tree_high_add_find_remove_nodes);
     cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
+    cx_test_register(suite, test_tree_high_add_find_without_loc_data);
+    cx_test_register(suite, test_tree_high_find_max_depth);
+    cx_test_register(suite, test_tree_high_find_fast);
     cx_test_register(suite, test_tree_high_remove_or_destroy_root);
     cx_test_register(suite, test_tree_high_simple_destructor);
     cx_test_register(suite, test_tree_high_iterator);
+    cx_test_register(suite, test_tree_high_iterator_large_depth);
     cx_test_register(suite, test_tree_high_visitor);
 
     return suite;