diff --git a/rust/hg-core/src/dirstate_tree/dirstate_map.rs b/rust/hg-core/src/dirstate_tree/dirstate_map.rs
--- a/rust/hg-core/src/dirstate_tree/dirstate_map.rs
+++ b/rust/hg-core/src/dirstate_tree/dirstate_map.rs
@@ -379,9 +379,14 @@
                     had_entry: node.entry.take().is_some(),
                     had_copy_source: node.copy_source.take().is_some(),
                 };
-                // TODO: this leaves in the tree a "non-file" node. Should we
-                // remove the node instead, together with ancestor nodes for
-                // directories that become empty?
+            }
+            // After recursion, for both leaf (rest_of_path is None) nodes and
+            // parent nodes, remove a node if it just became empty.
+            if node.entry.is_none()
+                && node.copy_source.is_none()
+                && node.children.is_empty()
+            {
+                nodes.remove(first_path_component);
             }
             Some(dropped)
         }
diff --git a/tests/test-status.t b/tests/test-status.t
--- a/tests/test-status.t
+++ b/tests/test-status.t
@@ -711,6 +711,9 @@
   $ hg rm b
   $ hg status a
   R a
+  $ hg commit -qm '#1'
+  $ hg status a
+  a: $ENOENT$
 
 Check using include flag with pattern when status does not need to traverse
 the working directory (issue6483)