diff --git a/src/engine/transaction.h b/src/engine/transaction.h
--- a/src/engine/transaction.h
+++ b/src/engine/transaction.h
@@ -26,6 +26,7 @@
 #include "postingdb.h"
 #include "writetransaction.h"
 #include "documenttimedb.h"
+#include <functional>
 
 #include <QString>
 #include <lmdb.h>
@@ -107,12 +108,12 @@
     void removeRecursively(quint64 parentId);
     void addFailed(quint64 id);
 
-    template <typename Functor>
-    void removeRecursively(quint64 id, Functor shouldDelete) {
+    bool removeRecursively(quint64 parentId, std::function<bool(quint64)> shouldDelete)
+    {
         Q_ASSERT(m_txn);
         Q_ASSERT(m_writeTrans);
 
-        m_writeTrans->removeRecursively(id, shouldDelete);
+        return m_writeTrans->removeRecursively(parentId, shouldDelete);
     }
 
     void replaceDocument(const Document& doc, DocumentOperations operations);
diff --git a/src/engine/writetransaction.h b/src/engine/writetransaction.h
--- a/src/engine/writetransaction.h
+++ b/src/engine/writetransaction.h
@@ -26,6 +26,7 @@
 #include "documentoperations.h"
 #include "databasedbis.h"
 #include "documenturldb.h"
+#include <functional>
 
 namespace Baloo {
 
@@ -51,27 +52,12 @@
      * through everything.
      *
      * \arg shouldDelete takes a quint64 as a parameter
+     * \ret true if the document (and all its children) has been removed
      *
      * This function should typically be called when there are no other ReadTransaction in process
      * as that would otherwise balloon the size of the database.
      */
-    template <typename Functor>
-    void removeRecursively(quint64 parentId, Functor shouldDelete) {
-        DocumentUrlDB docUrlDB(m_dbis.idTreeDbi, m_dbis.idFilenameDbi, m_txn);
-
-        if (!shouldDelete(parentId)) {
-            return;
-        }
-
-        const QVector<quint64> children = docUrlDB.getChildren(parentId);
-        for (quint64 id : children) {
-            removeRecursively(id, shouldDelete);
-        }
-        // refetch
-        if (docUrlDB.getChildren(parentId).isEmpty()) {
-            removeDocument(parentId);
-        }
-    }
+    bool removeRecursively(quint64 parentId, std::function<bool(quint64)> shouldDelete);
 
     void replaceDocument(const Document& doc, DocumentOperations operations);
     void commit();
diff --git a/src/engine/writetransaction.cpp b/src/engine/writetransaction.cpp
--- a/src/engine/writetransaction.cpp
+++ b/src/engine/writetransaction.cpp
@@ -167,6 +167,27 @@
     removeDocument(parentId);
 }
 
+bool WriteTransaction::removeRecursively(quint64 parentId, std::function<bool(quint64)> shouldDelete)
+{
+    DocumentUrlDB docUrlDB(m_dbis.idTreeDbi, m_dbis.idFilenameDbi, m_txn);
+
+    if (parentId && !shouldDelete(parentId)) {
+        return false;
+    }
+
+    bool isEmpty = true;
+    const QVector<quint64> children = docUrlDB.getChildren(parentId);
+    for (quint64 id : children) {
+        isEmpty &= removeRecursively(id, shouldDelete);
+    }
+    // refetch
+    if (isEmpty && docUrlDB.getChildren(parentId).isEmpty()) {
+        removeDocument(parentId);
+        return true;
+    }
+    return false;
+}
+
 void WriteTransaction::replaceDocument(const Document& doc, DocumentOperations operations)
 {
     DocumentDB documentTermsDB(m_dbis.docTermsDbi, m_txn);