Repository: pydata/xarray

Issue:
DataTree.from_dict fails to insert parent if parent/child inserted first.
### What happened?


`DataTree.from_dict()` fails to initialize if a parent/child node is inserted before a parent node


```python
lineage = DataTree.from_dict(
    {
        "/": xr.Dataset({"age": 83}),
        "/Homer": xr.Dataset({"age": 39}),
        "/Homer/Bart": xr.Dataset({"age": 10}),
    }
)
print(lineage)
```
works as expected:
```text
<xarray.DataTree>
Group: /
│   Dimensions:  ()
│   Data variables:
│       age      int64 8B 83
└── Group: /Homer
    │   Dimensions:  ()
    │   Data variables:
    │       age      int64 8B 39
    └── Group: /Homer/Bart
            Dimensions:  ()
            Data variables:
                age      int64 8B 10

```

If you reverse the dictionary

```python

DataTree.from_dict({
    "/Homer/Bart": xr.Dataset({"age": 10}),        
    "/Homer": xr.Dataset({"age": 39}),
    "/": xr.Dataset({"age": 83}),
})
```
It fails:
```text
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[40], line 1
----> 1 DataTree.from_dict({
      2     "/Homer/Bart": xr.Dataset({"age": 10}),        
      3     "/Homer": xr.Dataset({"age": 39}),
      4     "/": xr.Dataset({"age": 83}),
      5 })

File ~/projects/data-services/contrib/xarray/xarray/core/datatree.py:1115, in DataTree.from_dict(cls, d, name)
   1113         else:
   1114             new_node = cls(name=node_name, data=data)
-> 1115         obj._set_item(
   1116             path,
   1117             new_node,
   1118             allow_overwrite=False,
   1119             new_nodes_along_path=True,
   1120         )
   1122 return obj

File ~/projects/data-services/contrib/xarray/xarray/core/treenode.py:552, in TreeNode._set_item(self, path, item, new_nodes_along_path, allow_overwrite)
    550         current_node._set(name, item)
    551     else:
--> 552         raise KeyError(f"Already a node object at path {path}")
    553 else:
    554     current_node._set(name, item)

KeyError: 'Already a node object at path /Homer'
```

This might be easy, but unrelated to fixing the docs so I'm filing a bug report.


### What did you expect to happen?

I expect that the dictionary order should not affect the DataTree creation.


### Minimal Complete Verifiable Example

```Python
from xarray.core.datatree import DataTree

DataTree.from_dict({
    "/Homer/Bart": xr.Dataset({"age": 10}),        
    "/Homer": xr.Dataset({"age": 39}),
    "/": xr.Dataset({"age": 83}),
})
```


### MVCE confirmation

- [X] Minimal example — the example is as focused as reasonably possible to demonstrate the underlying issue in xarray.
- [X] Complete example — the example is self-contained, including all data and the text of any traceback.
- [X] Verifiable example — the example copy & pastes into an IPython prompt or [Binder notebook](https://mybinder.org/v2/gh/pydata/xarray/main?urlpath=lab/tree/doc/examples/blank_template.ipynb), returning the result.
- [X] New issue — a search of GitHub Issues suggests this is not a duplicate.
- [X] Recent environment — the issue occurs with the latest version of xarray and its dependencies.

### Relevant log output

```Python
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[40], line 1
----> 1 DataTree.from_dict({
      2     "/Homer/Bart": xr.Dataset({"age": 10}),        
      3     "/Homer": xr.Dataset({"age": 39}),
      4     "/": xr.Dataset({"age": 83}),
      5 })

File ~/projects/data-services/contrib/xarray/xarray/core/datatree.py:1115, in DataTree.from_dict(cls, d, name)
   1113         else:
   1114             new_node = cls(name=node_name, data=data)
-> 1115         obj._set_item(
   1116             path,
   1117             new_node,
   1118             allow_overwrite=False,
   1119             new_nodes_along_path=True,
   1120         )
   1122 return obj

File ~/projects/data-services/contrib/xarray/xarray/core/treenode.py:552, in TreeNode._set_item(self, path, item, new_nodes_along_path, allow_overwrite)
    550         current_node._set(name, item)
    551     else:
--> 552         raise KeyError(f"Already a node object at path {path}")
    553 else:
    554     current_node._set(name, item)

KeyError: 'Already a node object at path /Homer'
```


### Anything else we need to know?

_No response_

### Environment

<details>

/Users/savoie/.pyenv/versions/miniconda3-4.7.12/envs/xarray-tests/lib/python3.11/site-packages/_distutils_hack/__init__.py:26: UserWarning: Setuptools is replacing distutils.
  warnings.warn("Setuptools is replacing distutils.")

INSTALLED VERSIONS
------------------
commit: 068bab28bcaf8a5af25a229e6ec60b5647f983b2
python: 3.11.9 | packaged by conda-forge | (main, Apr 19 2024, 18:45:13) [Clang 16.0.6 ]
python-bits: 64
OS: Darwin
OS-release: 23.5.0
machine: x86_64
processor: i386
byteorder: little
LC_ALL: en_US.UTF-8
LANG: en_US.UTF-8
LOCALE: ('en_US', 'UTF-8')
libhdf5: 1.14.3
libnetcdf: 4.9.2

xarray: 2024.6.1.dev88+g068bab28b.d20240724
pandas: 2.2.2
numpy: 1.26.4
scipy: 1.13.0
netCDF4: 1.6.5
pydap: installed
h5netcdf: 1.3.0
h5py: 3.11.0
zarr: 2.17.2
cftime: 1.6.3
nc_time_axis: 1.4.1
iris: 3.9.0
bottleneck: 1.3.8
dask: 2024.4.2
distributed: 2024.4.2
matplotlib: 3.8.4
cartopy: 0.23.0
seaborn: 0.13.2
numbagg: 0.8.1
fsspec: 2024.3.1
cupy: None
pint: 0.23
sparse: 0.15.1
flox: 0.9.6
numpy_groupies: 0.10.2
setuptools: 69.5.1
pip: 24.0
conda: None
pytest: 8.1.1
mypy: 1.8.0
IPython: 8.25.0
sphinx: None


</details>


Discussion:
TomNicholas: The test failure is an unrelated flaky dask test so now I have an approval I will merge.

Patch:
diff --git a/doc/whats-new.rst b/doc/whats-new.rst
index e959ec11..0d146a7f 100644
--- a/doc/whats-new.rst
+++ b/doc/whats-new.rst
@@ -35,6 +35,8 @@ Deprecations
 Bug fixes
 ~~~~~~~~~
 
+- Fix bug causing `DataTree.from_dict` to be sensitive to insertion order (:issue:`9276`, :pull:`9292`).
+  By `Tom Nicholas <https://github.com/TomNicholas>`_.
 
 Documentation
 ~~~~~~~~~~~~~
diff --git a/xarray/core/datatree.py b/xarray/core/datatree.py
index 65ff8667..f8a8a5fb 100644
--- a/xarray/core/datatree.py
+++ b/xarray/core/datatree.py
@@ -1102,9 +1102,14 @@ class DataTree(
         else:
             obj = cls(name=name, data=root_data, parent=None, children=None)
 
+        def depth(item) -> int:
+            pathstr, _ = item
+            return len(NodePath(pathstr).parts)
+
         if d:
             # Populate tree with children determined from data_objects mapping
-            for path, data in d.items():
+            # Sort keys by depth so as to insert nodes from root first (see GH issue #9276)
+            for path, data in sorted(d.items(), key=depth):
                 # Create and set new node
                 node_name = NodePath(path).name
                 if isinstance(data, DataTree):


Test patch:
diff --git a/xarray/tests/test_datatree.py b/xarray/tests/test_datatree.py
index 31d77ca1..c875322b 100644
--- a/xarray/tests/test_datatree.py
+++ b/xarray/tests/test_datatree.py
@@ -561,6 +561,30 @@ class TestTreeFromDict:
         roundtrip = DataTree.from_dict(dt.to_dict())
         assert roundtrip.equals(dt)
 
+    def test_insertion_order(self):
+        # regression test for GH issue #9276
+        reversed = DataTree.from_dict(
+            {
+                "/Homer/Lisa": xr.Dataset({"age": 8}),
+                "/Homer/Bart": xr.Dataset({"age": 10}),
+                "/Homer": xr.Dataset({"age": 39}),
+                "/": xr.Dataset({"age": 83}),
+            }
+        )
+        expected = DataTree.from_dict(
+            {
+                "/": xr.Dataset({"age": 83}),
+                "/Homer": xr.Dataset({"age": 39}),
+                "/Homer/Lisa": xr.Dataset({"age": 8}),
+                "/Homer/Bart": xr.Dataset({"age": 10}),
+            }
+        )
+        assert reversed.equals(expected)
+
+        # Check that Bart and Lisa's order is still preserved within the group,
+        # despite 'Bart' coming before 'Lisa' when sorted alphabetically
+        assert list(reversed["Homer"].children.keys()) == ["Lisa", "Bart"]
+
 
 class TestDatasetView:
     def test_view_contents(self):