diff --git a/ebtree/ebtree.h b/ebtree/ebtree.h
index cfb7851..bc8012d 100644
--- a/ebtree/ebtree.h
+++ b/ebtree/ebtree.h
@@ -615,12 +615,16 @@
 		t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
 	}
 
-	/* Note that <t> cannot be NULL at this stage */
+	/* Note that <t> cannot be NULL at this stage. If our leaf is directly
+	 * under the root, we must not try to cast the leaf_p into a eb_node*
+	 * since it is a pointer to an eb_root.
+	 */
+	if (eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL)
+		return NULL;
+
 	if ((eb_root_to_node(eb_untag(t, EB_LEFT)))->bit >= 0)
 		return NULL;
 	t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
-	if (eb_clrtag(t) == NULL)
-		return NULL;
 	return eb_walk_down(t, EB_LEFT);
 }