This is an implementation detail of find. You'll find the ultimate answer to your question in it's source code.
On Linux another way to understand what is happening behind the scenes is strace. I've prepared some interesting output from strace below. You may have a look at the order of the openat system calls issues by both find invocations (with and without -depth):
mkdir -pv TOP{1,2}/AB/AC/AD/AE/AF && strace -o foo find . -depth -iname 'A*' -exec rm -rvf {} \; ; grep openat foo
mkdir: created directory 'TOP1/AB'
mkdir: created directory 'TOP1/AB/AC'
mkdir: created directory 'TOP1/AB/AC/AD'
mkdir: created directory 'TOP1/AB/AC/AD/AE'
mkdir: created directory 'TOP1/AB/AC/AD/AE/AF'
mkdir: created directory 'TOP2/AB'
mkdir: created directory 'TOP2/AB/AC'
mkdir: created directory 'TOP2/AB/AC/AD'
mkdir: created directory 'TOP2/AB/AC/AD/AE'
mkdir: created directory 'TOP2/AB/AC/AD/AE/AF'
removed directory './TOP1/AB/AC/AD/AE/AF'
removed directory './TOP1/AB/AC/AD/AE'
removed directory './TOP1/AB/AC/AD'
removed directory './TOP1/AB/AC'
removed directory './TOP1/AB'
removed directory './TOP2/AB/AC/AD/AE/AF'
removed directory './TOP2/AB/AC/AD/AE'
removed directory './TOP2/AB/AC/AD'
removed directory './TOP2/AB/AC'
removed directory './TOP2/AB'
5:openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
9:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libselinux.so.1", O_RDONLY|O_CLOEXEC) = 3
20:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libm.so.6", O_RDONLY|O_CLOEXEC) = 3
28:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
44:openat(AT_FDCWD, "/usr/lib/x86_64-linux-gnu/libpcre2-8.so.0", O_RDONLY|O_CLOEXEC) = 3
52:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libdl.so.2", O_RDONLY|O_CLOEXEC) = 3
60:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libpthread.so.0", O_RDONLY|O_CLOEXEC) = 3
93:openat(AT_FDCWD, "/proc/filesystems", O_RDONLY|O_CLOEXEC) = 3
99:openat(AT_FDCWD, ".", O_RDONLY|O_CLOEXEC) = 3
102:openat(AT_FDCWD, "/usr/lib/locale/locale-archive", O_RDONLY|O_CLOEXEC) = 4
106:openat(AT_FDCWD, "/usr/lib/x86_64-linux-gnu/gconv/gconv-modules.cache", O_RDONLY) = 4
114:openat(AT_FDCWD, ".", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 4
125:openat(5, "TOP1", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
137:openat(7, "AB", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
149:openat(8, "AC", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
161:openat(9, "AD", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
173:openat(10, "AE", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
186:openat(11, "AF", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
223:openat(8, "..", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
231:openat(5, "..", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
237:openat(6, "TOP2", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
249:openat(7, "AB", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
261:openat(8, "AC", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
273:openat(9, "AD", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
285:openat(10, "AE", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
298:openat(11, "AF", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
332:openat(8, "..", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 5
340:openat(5, "..", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
mkdir -pv TOP{1,2}/AB/AC/AD/AE/AF && strace -o foo find . -iname 'A*' -exec rm -rvf {} \; ; grep openat foo
mkdir: created directory 'TOP1/AB'
mkdir: created directory 'TOP1/AB/AC'
mkdir: created directory 'TOP1/AB/AC/AD'
mkdir: created directory 'TOP1/AB/AC/AD/AE'
mkdir: created directory 'TOP1/AB/AC/AD/AE/AF'
mkdir: created directory 'TOP2/AB'
mkdir: created directory 'TOP2/AB/AC'
mkdir: created directory 'TOP2/AB/AC/AD'
mkdir: created directory 'TOP2/AB/AC/AD/AE'
mkdir: created directory 'TOP2/AB/AC/AD/AE/AF'
removed directory './TOP1/AB/AC/AD/AE/AF'
removed directory './TOP1/AB/AC/AD/AE'
removed directory './TOP1/AB/AC/AD'
removed directory './TOP1/AB/AC'
removed directory './TOP1/AB'
find: ‘./TOP1/AB’: No such file or directory
removed directory './TOP2/AB/AC/AD/AE/AF'
removed directory './TOP2/AB/AC/AD/AE'
removed directory './TOP2/AB/AC/AD'
removed directory './TOP2/AB/AC'
removed directory './TOP2/AB'
find: ‘./TOP2/AB’: No such file or directory
5:openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
9:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libselinux.so.1", O_RDONLY|O_CLOEXEC) = 3
20:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libm.so.6", O_RDONLY|O_CLOEXEC) = 3
28:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
44:openat(AT_FDCWD, "/usr/lib/x86_64-linux-gnu/libpcre2-8.so.0", O_RDONLY|O_CLOEXEC) = 3
52:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libdl.so.2", O_RDONLY|O_CLOEXEC) = 3
60:openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libpthread.so.0", O_RDONLY|O_CLOEXEC) = 3
93:openat(AT_FDCWD, "/proc/filesystems", O_RDONLY|O_CLOEXEC) = 3
99:openat(AT_FDCWD, ".", O_RDONLY|O_CLOEXEC) = 3
102:openat(AT_FDCWD, "/usr/lib/locale/locale-archive", O_RDONLY|O_CLOEXEC) = 4
106:openat(AT_FDCWD, "/usr/lib/x86_64-linux-gnu/gconv/gconv-modules.cache", O_RDONLY) = 4
114:openat(AT_FDCWD, ".", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 4
125:openat(5, "TOP1", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
142:openat(7, "AB", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = -1 ENOENT (No such file or directory)
143:openat(AT_FDCWD, "/usr/share/locale/locale.alias", O_RDONLY|O_CLOEXEC) = 6
148:openat(AT_FDCWD, "/usr/share/locale/en_US/LC_MESSAGES/findutils.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
149:openat(AT_FDCWD, "/usr/share/locale/en/LC_MESSAGES/findutils.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
150:openat(AT_FDCWD, "/usr/share/locale-langpack/en_US/LC_MESSAGES/findutils.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
151:openat(AT_FDCWD, "/usr/share/locale-langpack/en/LC_MESSAGES/findutils.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
154:openat(AT_FDCWD, "/usr/share/locale/en_US/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
155:openat(AT_FDCWD, "/usr/share/locale/en/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
156:openat(AT_FDCWD, "/usr/share/locale-langpack/en_US/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
157:openat(AT_FDCWD, "/usr/share/locale-langpack/en/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
164:openat(5, "TOP2", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = 6
179:openat(7, "AB", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_NOFOLLOW|O_CLOEXEC|O_DIRECTORY) = -1 ENOENT (No such file or directory)