A generic tree data structure.

Tree.cs

using System;
using System.Collections.Generic;
using UnityEngine;

[Serializable]
public class Tree<T>
{
    [Serializable]
    private struct Node
    {
        public T data;
        public int id;
        public int parentId;
        public int siblingIndex;
        public List<int> children;
    }

    [SerializeField]
    private List<Node> _nodes = new();
    [SerializeField]
    private  List<int> _freeList = new();
    [SerializeField]
    private  List<int> _roots = new();
    [SerializeField]
    private int _idCounter;

    /// <summary>
    /// Create a new node with the given data and (optionally) add it to the parent ID.
    /// </summary>
    /// <param name="data"></param>
    /// <param name="parentId"></param>
    /// <param name="index"></param>
    /// <returns></returns>
    public int CreateNode(T data, int parentId = -1, int index = -1)
    {
        var node = new Node
        {
            data = data,
            id = NextID(),
            parentId = parentId,
            siblingIndex = int.MinValue, 
            children = new List<int>()
        };
        _nodes[node.id] = node;
        
        List<int> children;

        if (parentId == -1)
        {
            children = _roots;
        }
        else
        {
            ValidateNodeId(parentId);
            children = _nodes[parentId].children;
        }

        if (index < 0 || index >= children.Count)
            index = children.Count;
        
        children.Insert(index, node.id);
        UpdateSiblingIndexOfChildren(children);
        
        return node.id;
    }

    /// <summary>
    /// Returns the data object of the node.
    /// </summary>
    /// <param name="id"></param>
    /// <returns></returns>
    public T GetData(int id)
    {
        ValidateNodeId(id);
        return _nodes[id].data;
    }

    /// <summary>
    /// Sets the data object of the node.
    /// </summary>
    /// <param name="id"></param>
    /// <param name="data"></param>
    public void SetData(int id, T data)
    {
        ValidateNodeId(id);
        var node = _nodes[id];
        node.data = data;
        _nodes[id] = node; // Reassigning the modified struct
    }

    /// <summary>
    /// Add a child node to the parent node at (optional) index.
    /// </summary>
    /// <param name="parentId"></param>
    /// <param name="childId"></param>
    /// <param name="index"></param>
    /// <exception cref="ArgumentException"></exception>
    public void AddChild(int parentId, int childId, int index = -1)
    {
        ValidateNodeId(childId);
        
        if (parentId == childId)
            throw new System.ArgumentException("Parent ID cannot be the same as child ID");

        var child = _nodes[childId];
        
        var oldParentId = child.parentId;
        var newParentId = parentId;
        
        if (oldParentId == newParentId) // This is just a reorder operation, so perform the reorder and exit.
        {
            SetSiblingIndex(childId, index);
            return;
        }

        if (oldParentId == -1) // If this child is a root, remove this child from the list of roots
        {
            _roots.Remove(childId);
        }
        else // Remove this child from the old parent.
        {
            var oldParent = _nodes[oldParentId];
            oldParent.children.Remove(childId);
            UpdateSiblingIndexOfChildren(oldParent.children);
            _nodes[oldParentId] = oldParent;
        }

        if(newParentId == -1) // This child is becoming a root node
        {
            if(index < 0)
                _roots.Add(childId);
            else
                _roots.Insert(index, childId);
            child.parentId = -1;
            child.siblingIndex = int.MinValue;
            _nodes[childId] = child; // Reassigning the modified child struct
            UpdateSiblingIndexOfChildren(_roots);
        }
        else // This child has a new parent
        {
            ValidateNodeId(newParentId);
            
            var newParent = _nodes[newParentId];
     
            // Add child to the new parent
            if (index < 0)
                newParent.children.Add(childId);
            else 
                newParent.children.Insert(index, childId);
        
            // Update the child's parent ID 
            child.parentId = newParentId;
            _nodes[child.id] = child; // Reassigning the modified child struct
            UpdateSiblingIndexOfChildren(newParent.children);
            _nodes[newParentId] = newParent; // Reassigning the modified parent struct    
        }
        
        
    }

    /// <summary>
    /// Return the root nodes of the tree.
    /// </summary>
    /// <returns></returns>
    public IEnumerable<int> GetRoots()
    {
        return _roots;
    }

    /// <summary>
    /// Return the parent ID of the child node.
    /// </summary>
    /// <param name="childId"></param>
    /// <returns></returns>
    public int GetParent(int childId)
    {
        ValidateNodeId(childId);
        return _nodes[childId].parentId;
    }

    /// <summary>
    /// Remove a node and all it's children from the tree.
    /// </summary>
    /// <param name="id"></param>
    public void RemoveNode(int id)
    {
        ValidateNodeId(id);
        var removeList = new List<int>();
        var stack = new Stack<int>();
        stack.Push(id);
        while (stack.Count > 0)
        {
            var currentId = stack.Pop();
            foreach (var childId in GetChildren(currentId))
            {
                stack.Push(childId);
            }
            removeList.Add(currentId);
        }

        var parentId = GetParent(id);
        if (parentId != -1)
        {
            var parent = _nodes[parentId];
            parent.children.Remove(id);
            _nodes[parentId] = parent; // Reassigning the modified parent struct
            UpdateSiblingIndexOfChildren(parent.children);
        }
        else
        {
            _roots.Remove(id);
        }
        foreach(var removeId in removeList)
        {
            _nodes[removeId] = new Node() { id = -1, children = default, parentId = -1, data = default, siblingIndex = -1 }; // Mark this node as deleted using id = -1
            _freeList.Add(removeId);
        }
    }

    /// <summary>
    /// Returns true if the tree contains a node with the given ID.
    /// </summary>
    /// <param name="id"></param>
    /// <returns></returns>
    public bool Contains(int id)
    {
        return id >= 0 && id < _nodes.Count && _nodes[id].id == id;
    }

    /// <summary>
    /// Returns the children of the node with the given ID.
    /// </summary>
    /// <param name="id"></param>
    /// <returns></returns>
    public IEnumerable<int> GetChildren(int id)
    {
        ValidateNodeId(id);
        return _nodes[id].children;
    }
    
    /// <summary>
    /// Returns the number of children of the node with the given ID.
    /// </summary>
    /// <param name="id"></param>
    /// <returns></returns>
    public int GetChildCount(int id)
    {
        ValidateNodeId(id);
        return _nodes[id].children.Count;
    }

    /// <summary>
    /// Clears all nodes from the tree.
    /// </summary>
    public void Clear()
    {
        _nodes.Clear();
        _freeList.Clear();
        _roots.Clear();
        _idCounter = 0;
    }

    /// <summary>
    /// Returns number of nodes in the tree.
    /// </summary>
    public int Count => _nodes.Count - _freeList.Count;
    
    /// <summary>
    /// Returns the sibling index (order) of the node with the given ID.
    /// </summary>
    /// <param name="id"></param>
    /// <returns></returns>
    public int GetSiblingIndex(int id)
    {
        ValidateNodeId(id);
        return _nodes[id].siblingIndex;
    }
    
    /// <summary>
    /// Returns true if the node with the given ID is a descendant of the node with the given parent ID.
    /// </summary>
    /// <param name="id"></param>
    /// <param name="parentId"></param>
    /// <returns></returns>
    public bool IsDescendantOf(int id, int parentId)
    {
        if (id == parentId)
            return true;
        var parent = GetParent(id);
        while (parent != -1)
        {
            if (parent == parentId)
                return true;
            parent = GetParent(parent);
        }
        return false;
    }

    /// <summary>
    /// Copy a node and all its children to a new tree.
    /// </summary>
    /// <param name="id"></param>
    /// <returns></returns>
    public Tree<T> CopySubtree(int id)
    {
        //Create a new tree and copy the children recursively
        var tree = new Tree<T>();
        
        void CopyChildren(int parentToCopy, int newParent)
        {
            //iterate all the children in the existing tree
            foreach(var childToCopy in GetChildren(parentToCopy))
            {
                //and copy them to the new tree
                var newChild = tree.CreateNode(GetData(childToCopy), newParent);
                CopyChildren(childToCopy, newChild);
            }
        }
        
        //Create the root node and copy the children
        var root = tree.CreateNode(GetData(id));
        CopyChildren(id, root);
        return tree;
    }

    /// <summary>
    /// Copy all root nodes from another tree to a node in this tree.
    /// </summary>
    /// <param name="id"></param>
    /// <param name="subtree"></param>
    /// <param name="index"></param>
    public void AddSubtree(int id, Tree<T> subtree, int index=-1)
    {
        void CopyTree(int parentToCopy, int newParent)
        {
            //iterate all the children in the sub tree
            foreach(var childToCopy in subtree.GetChildren(parentToCopy))
            {
                //and copy them to the existing tree
                var newChild = CreateNode(subtree.GetData(childToCopy), newParent);
                CopyTree(childToCopy, newChild);
            }
        }
        //create the root node and copy the children
        foreach(var rootId in subtree.GetRoots())
        {
            var newRoot = CreateNode(subtree.GetData(rootId));
            AddChild(id, newRoot, index);
            CopyTree(rootId, newRoot);
        }
        
    }
    
    /// <summary>
    /// Set the sibling index of the node with the given ID.
    /// </summary>
    /// <param name="id"></param>
    /// <param name="index"></param>
    public void SetSiblingIndex(int id, int index)
    {
        ValidateNodeId(id);
        var node = _nodes[id];
        List<int> children;
        if (node.parentId == -1) //This is a root node, so work on the list of roots.
            children = _roots;
        else //This is a child node, so work on the list of children.
            children = _nodes[node.parentId].children;
        
        if(index < 0 || index >= children.Count)
            index = children.Count;
        
        var siblingIndex = node.siblingIndex;
        if (siblingIndex == index)
            return;
        //0, 1
        //A B C
        
        //if(siblingIndex < index)
        //    index--;
        children.RemoveAt(siblingIndex);
        children.Insert(index, id);
        UpdateSiblingIndexOfChildren(children);
        
    }
    
    private void UpdateSiblingIndexOfChildren(List<int> children)
    {
        for (var i = 0; i < children.Count; i++)
        {
            var childId = children[i];
            var child = _nodes[childId];
            child.siblingIndex = i;
            _nodes[childId] = child;
        }
    }

    private void ValidateNodeId(int id)
    {
        if (!Contains(id))
            throw new ArgumentException($"Invalid ID: {id}");
    }

    private int NextID()
    {
        var freeListCount = _freeList.Count;
        if (freeListCount <= 0)
        {
            _nodes.Add(new Node());
            return _idCounter++;
        }
        var id = _freeList[freeListCount - 1];
        _freeList.RemoveAt(freeListCount - 1);
        return id;
    }
    
}

TreeAsset.cs

using UnityEngine;

[CreateAssetMenu(fileName = "TreeAsset", menuName = "Scriptable Objects/TreeAsset")]
public class TreeAsset : ScriptableObject
{
    public Tree<string> tree;
    
    private void OnEnable()
    {
        if (tree == null)
        {
            tree = new Tree<string>();
        }
        if(tree.Count == 0)
        {
            BuildTestData();
        }
    }
    
    //This method is used to build the data model for the example.
    void BuildTestData()
    {
        if (tree.Count > 0)
        {
            //Don't rebuild the data model if it already has data. 
            return;
        }
        tree.Clear();
        var root = tree.CreateNode("Root Node 0");
        for(var i = 0; i < 2; i++)
        {
            var node = tree.CreateNode($"Node {i}", parentId: root);
            for(var j = 0; j < 2; j++)
            {
                var item = tree.CreateNode($"Node {i}.{j}", parentId: node);
                for(var k = 0; k < 2; k++)
                {
                    tree.CreateNode($"Node {i}.{j}.{k}", parentId: item);
                }
            }
        }
    }

    public void Reset()
    {
        tree.Clear();
        BuildTestData();
    }
}

TreeModelTests.cs

using NUnit.Framework;
using System.Collections.Generic;
using UnityEngine;

namespace TreeModelTests
{
    public class TreeModelTests
    {
        private Tree<string> tree;

        [SetUp]
        public void SetUp()
        {
            tree = new Tree<string>();
        }

        [Test]
        public void CreateNode_ShouldReturnUniqueId()
        {
            var id1 = tree.CreateNode("Root");
            var id2 = tree.CreateNode("Child");

            Assert.AreNotEqual(id1, id2);
        }

        [Test]
        public void GetData_ShouldReturnCorrectData()
        {
            var id = tree.CreateNode("Root");

            var data = tree.GetData(id);

            Assert.AreEqual("Root", data);
        }

        [Test]
        public void SetData_ShouldUpdateNodeData()
        {
            var id = tree.CreateNode("Root");
            tree.SetData(id, "UpdatedRoot");

            var data = tree.GetData(id);

            Assert.AreEqual("UpdatedRoot", data);
        }

        [Test]
        public void AddChild_ShouldEstablishParentChildRelationship()
        {
            var parentId = tree.CreateNode("Parent");
            var childId = tree.CreateNode("Child");

            tree.AddChild(parentId, childId);

            Assert.AreEqual(parentId, tree.GetParent(childId));
            CollectionAssert.Contains(tree.GetChildren(parentId), childId);
        }

        [Test]
        public void RemoveNode_ShouldDeleteNodeAndChildren()
        {
            var parentId = tree.CreateNode("Parent");
            var childId = tree.CreateNode("Child");

            tree.AddChild(parentId, childId);
            tree.RemoveNode(parentId);

            Assert.IsFalse(tree.Contains(parentId));
            Assert.IsFalse(tree.Contains(childId));
        }

        [Test]
        public void Contains_ShouldReturnTrueForExistingNode()
        {
            var id = tree.CreateNode("Node");

            Assert.IsTrue(tree.Contains(id));
        }

        [Test]
        public void Contains_ShouldReturnFalseForDeletedNode()
        {
            var id = tree.CreateNode("Node");
            tree.RemoveNode(id);

            Assert.IsFalse(tree.Contains(id));
        }

        [Test]
        public void AddChild_ShouldThrowExceptionForInvalidParentId()
        {
            var invalidParentId = 7632;
            var childId = tree.CreateNode("Child");

            Assert.Throws<System.ArgumentException>(() => tree.AddChild(invalidParentId, childId));
        }

        [Test]
        public void AddChild_ShouldThrowExceptionForSelfParenting()
        {
            var id = tree.CreateNode("Node");

            Assert.Throws<System.ArgumentException>(() => tree.AddChild(id, id));
        }

        [Test]
        public void GetChildren_ShouldReturnEmptyForNodeWithoutChildren()
        {
            var id = tree.CreateNode("Node");

            CollectionAssert.IsEmpty(tree.GetChildren(id));
        }

        [Test]
        public void RemoveNode_ShouldReuseIdsFromFreeList()
        {
            var id1 = tree.CreateNode("Node1");
            tree.RemoveNode(id1);

            var id2 = tree.CreateNode("Node2");

            Assert.AreEqual(id1, id2);
        }
        
        [Test]
        public void RemoveNode_ShouldMarkNodesAsDeletedAndReuseIds()
        {
            var rootId = tree.CreateNode("Root");
            var childId = tree.CreateNode("Child");

            tree.AddChild(rootId, childId);
            tree.RemoveNode(childId);

            Assert.IsFalse(tree.Contains(childId));
        
            var newId = tree.CreateNode("NewChild");
            Assert.AreEqual(childId, newId); // The ID should be reused
        }
        
        [Test]
        public void AddChildren_CheckOrder()
        {
            var rootId = tree.CreateNode("root");
            var child1 = tree.CreateNode("child1");
            var child2 = tree.CreateNode("child2");
            var child3 = tree.CreateNode("child3");

            tree.AddChild(rootId, child1);
            tree.AddChild(rootId, child2);
            tree.AddChild(rootId, child3);

            var children = new List<int>(tree.GetChildren(rootId));
            Assert.AreEqual(new List<int> { child1, child2, child3 }, children, "Children should be in the order they were added");
        }

        [Test]
        public void InsertChildAtSpecificIndex_CheckOrder()
        {
            var rootId = tree.CreateNode("root");
            var child1 = tree.CreateNode("child1");
            var child2 = tree.CreateNode("child2");
            var child3 = tree.CreateNode("child3");

            tree.AddChild(rootId, child1);
            tree.AddChild(rootId, child2);
            tree.AddChild(rootId, child3, index: 1); // Insert child3 at index 1

            var children = new List<int>(tree.GetChildren(rootId));
            Assert.AreEqual(new List<int> { child1, child3, child2 }, children, "Children should reflect the correct insertion order");
        }

        [Test]
        public void RemoveChild_CheckOrderAfterRemoval()
        {
            var rootId = tree.CreateNode("root");
            var child1 = tree.CreateNode("child1");
            var child2 = tree.CreateNode("child2");
            var child3 = tree.CreateNode("child3");

            tree.AddChild(rootId, child1);
            tree.AddChild(rootId, child2);
            tree.AddChild(rootId, child3);

            tree.RemoveNode(child2);

            var children = new List<int>(tree.GetChildren(rootId));
            Assert.AreEqual(new List<int> { child1, child3 }, children, "Children should reflect the correct order after removing a node");
        }

        [Test]
        public void ReparentChild_CheckOrderInBothParents()
        {
            var rootId = tree.CreateNode("root");
            var child1 = tree.CreateNode("child1");
            var newParent = tree.CreateNode("newParent");

            tree.AddChild(rootId, child1);
            Assert.AreEqual(new List<int> { child1 }, new List<int>(tree.GetChildren(rootId)), "Initial parent should have child1");

            tree.AddChild(newParent, child1); // Reparent child1 to newParent

            Assert.AreEqual(new List<int>(), new List<int>(tree.GetChildren(rootId)), "Old parent should no longer have child1");
            Assert.AreEqual(new List<int> { child1 }, new List<int>(tree.GetChildren(newParent)), "New parent should now have child1");
        }

        [Test]
        public void AddMultipleChildren_UpdateOrder()
        {
            var rootId = tree.CreateNode("root");
            var child1 = tree.CreateNode("child1");
            var child2 = tree.CreateNode("child2");
            var child3 = tree.CreateNode("child3");

            tree.AddChild(rootId, child1);
            tree.AddChild(rootId, child2);
            tree.AddChild(rootId, child3);

            var children = new List<int>(tree.GetChildren(rootId));

            // Verify initial order
            Assert.AreEqual(new List<int> { child1, child2, child3 }, children, "Children should be in the correct initial order");

            // Verify the order field of each child
            Assert.AreEqual(0, tree.GetSiblingIndex(child1), "Order of child1 should be 0");
            Assert.AreEqual(1, tree.GetSiblingIndex(child2), "Order of child2 should be 1");
            Assert.AreEqual(2, tree.GetSiblingIndex(child3), "Order of child3 should be 2");
        }
        
        [Test]
        public void SiblingIndex_Updates_After_Removing_First_Child()
        {
            // Arrange
            var parent = tree.CreateNode("0");
            var child1 = tree.CreateNode("1");
            var child2 = tree.CreateNode("2");
            var child3 = tree.CreateNode("3");

            tree.AddChild(parent, child1);
            tree.AddChild(parent, child2);
            tree.AddChild(parent, child3);

            // Act
            tree.RemoveNode(child1);

            // Assert
            Assert.AreEqual(0, tree.GetSiblingIndex(child2));
            Assert.AreEqual(1, tree.GetSiblingIndex(child3));
        }

        [Test]
        public void SiblingIndex_Updates_After_Removing_Middle_Child()
        {
            // Arrange
            var parent = tree.CreateNode("0");
            var child1 = tree.CreateNode("1");
            var child2 = tree.CreateNode("2");
            var child3 = tree.CreateNode("3");

            tree.AddChild(parent, child1);
            tree.AddChild(parent, child2);
            tree.AddChild(parent, child3);

            // Act
            tree.RemoveNode(child2);

            // Assert
            Assert.AreEqual(0, tree.GetSiblingIndex(child1));
            Assert.AreEqual(1, tree.GetSiblingIndex(child3));
        }

        [Test]
        public void SiblingIndex_Updates_After_Removing_Last_Child()
        {
            // Arrange
            var parent = tree.CreateNode("0");
            var child1 = tree.CreateNode("1");
            var child2 = tree.CreateNode("2");
            var child3 = tree.CreateNode("3");

            tree.AddChild(parent, child1);
            tree.AddChild(parent, child2);
            tree.AddChild(parent, child3);

            // Act
            tree.RemoveNode(child3);

            // Assert
            Assert.AreEqual(0, tree.GetSiblingIndex(child1));
            Assert.AreEqual(1, tree.GetSiblingIndex(child2));
        }
        
        [Test]
        public void SiblingIndex_Updates_After_Reparenting()
        {
            // Arrange
            var parent1 = tree.CreateNode("0");
            var parent2 = tree.CreateNode("1");
            var child1 = tree.CreateNode("2");

            tree.AddChild(parent1, child1);

            // Act
            tree.AddChild(parent2, child1);

            // Assert
            Assert.AreEqual(0, tree.GetSiblingIndex(child1));
        }
        
        [Test]
        public void SiblingIndex_Updates_After_Inserting_Child_At_Index()
        {
            // Arrange
            var parent = tree.CreateNode("0");
            var child1 = tree.CreateNode("1");
            var child2 = tree.CreateNode("2");
            var child3 = tree.CreateNode("3");

            tree.AddChild(parent, child1);
            tree.AddChild(parent, child2);
            tree.AddChild(parent, child3, index: 1);

            // Assert
            Assert.AreEqual(0, tree.GetSiblingIndex(child1));
            Assert.AreEqual(1, tree.GetSiblingIndex(child3));
            Assert.AreEqual(2, tree.GetSiblingIndex(child2));
        }
        
        [Test]
        public void SiblingIndex_Updates_After_Reparenting_And_Inserting_Child_At_Index()
        {
            // Arrange
            var parent1 = tree.CreateNode("0");
            var parent2 = tree.CreateNode("1");
            var child1 = tree.CreateNode("2");
            var child2 = tree.CreateNode("3");

            tree.AddChild(parent1, child1);
            tree.AddChild(parent2, child2);
            tree.AddChild(parent1, child2, index: 0);

            // Assert
            Assert.AreEqual(0, tree.GetSiblingIndex(child2));
            Assert.AreEqual(1, tree.GetSiblingIndex(child1));
        }
        
        [Test]
        public void SubtreeCopy_CheckOrder()
        {
            // Arrange
            var rootId = tree.CreateNode("root");
            var child1 = tree.CreateNode("child1");
            var child2 = tree.CreateNode("child2");
            var child3 = tree.CreateNode("child3");

            tree.AddChild(rootId, child1);
            tree.AddChild(rootId, child2);
            tree.AddChild(rootId, child3);

            // Act
            var copiedTree = tree.CopySubtree(rootId);

            // Assert
            var copiedChildren = new List<int>(copiedTree.GetChildren(0));
            Assert.AreEqual(new List<int> { 1, 2, 3 }, copiedChildren, "Copied children should be in the correct order");
        }
        
        [Test]
        public void SubtreeCopy_CheckData()
        {
            // Arrange
            var rootId = tree.CreateNode("root");
            var child1 = tree.CreateNode("child1");
            var child2 = tree.CreateNode("child2");
            var child3 = tree.CreateNode("child3");

            tree.AddChild(rootId, child1);
            tree.AddChild(rootId, child2);
            tree.AddChild(rootId, child3);

            // Act
            var copiedTree = tree.CopySubtree(rootId);

            // Assert
            Assert.AreEqual("root", copiedTree.GetData(0), "Root data should be copied");
            Assert.AreEqual("child1", copiedTree.GetData(1), "Child1 data should be copied");
            Assert.AreEqual("child2", copiedTree.GetData(2), "Child2 data should be copied");
            Assert.AreEqual("child3", copiedTree.GetData(3), "Child3 data should be copied");
        }
        
        [Test]
        public void SubtreeCopy_CheckParentChildRelationship()
        {
            // Arrange
            var rootId = tree.CreateNode("root");
            var child1 = tree.CreateNode("child1");
            var child2 = tree.CreateNode("child2");
            var child3 = tree.CreateNode("child3");

            tree.AddChild(rootId, child1);
            tree.AddChild(rootId, child2);
            tree.AddChild(rootId, child3);

            // Act
            var copiedTree = tree.CopySubtree(rootId);

            // Assert
            Assert.AreEqual(0, copiedTree.GetParent(1), "Child1 should have root as parent");
            Assert.AreEqual(0, copiedTree.GetParent(2), "Child2 should have root as parent");
            Assert.AreEqual(0, copiedTree.GetParent(3), "Child3 should have root as parent");
        }
        
        [Test]
        public void CheckMultiRootOrder()
        {
            var root1 = tree.CreateNode("root1");
            var root2 = tree.CreateNode("root2");
            var root3 = tree.CreateNode("root3");
            var roots = new List<int>(tree.GetRoots());
            Assert.AreEqual(new List<int> { root1, root2, root3 }, roots, "Roots should be in the order they were added");
            tree.RemoveNode(root2);
            Assert.AreEqual(new List<int> { root1, root3 }, new List<int>(tree.GetRoots()), "Roots should be in the correct order after removing a root");
            var root4 = tree.CreateNode("root4");
            Assert.AreEqual(new List<int> { root1, root3, root4 }, new List<int>(tree.GetRoots()), "Roots should be in the correct order after adding a new root");
            tree.SetSiblingIndex(root4, 0);
            Assert.AreEqual(new List<int> { root4, root1, root3 }, new List<int>(tree.GetRoots()), "Roots should be in the correct order after changing the sibling index of a root");
            tree.SetSiblingIndex(root4, 1);
            Assert.AreEqual(new List<int> { root1, root4, root3 }, new List<int>(tree.GetRoots()), "Roots should be in the correct order after changing the sibling index of a root");
            tree.SetSiblingIndex(root3, 1);
            Assert.AreEqual(new List<int> { root1, root3, root4 }, new List<int>(tree.GetRoots()), "Roots should be in the correct order after changing the sibling index of a root");
        }
        
        [Test]
        public void CheckMultiRootOrderAfterReparenting()
        {
            var root1 = tree.CreateNode("root1");
            var root2 = tree.CreateNode("root2");
            var root3 = tree.CreateNode("root3");
            tree.RemoveNode(root2);
            var root4 = tree.CreateNode("root4");
            //root1, roo3, root4
            tree.SetSiblingIndex(root4, 0);
            //root4, root1, root3
            tree.SetSiblingIndex(root4, 1);
            //root1, root4, root3
            tree.SetSiblingIndex(root3, 1);
            //root1, root3, root4
            tree.AddChild(root1, root4);
            // root1. root3
            Assert.AreEqual(new List<int> { root1, root3 }, new List<int>(tree.GetRoots()), "Roots should be in the correct order after reparenting a root");
        }

        [Test]
        public void RemoveNodeShouldThrowExceptionWhenReused()
        {
            var root1 = tree.CreateNode("root1");
            var root2 = tree.CreateNode("root2");
            tree.RemoveNode(root2);
            var root3 = tree.CreateNode("root3");
            // This will not actually throw an exception, because root3 will be re-assigned the same ID as root2
            //Assert.Throws<System.ArgumentException>(() => tree.AddChild(root1, root2));
        }

    }
}

TreeViewEditorExample.cs

using System;
using System.Collections.Generic;
using UnityEditor;
using UnityEditor.Callbacks;
using UnityEngine;
using UnityEngine.UIElements;


public class TreeViewEditorExample : EditorWindow
{
    //This is the data model, where things can be serialized.
    [SerializeField] private TreeAsset dataModel;
    
    //This is the clipboard used for cut, copy, paste.
    [SerializeField] private Tree<string> clipboardTree;
    
    //This is the tree view that displays the data model.
    private TreeView treeView;
    
    //Handles opening the editor window when double-clicking project files
    [OnOpenAsset]
    private static bool OnOpenAsset(int instanceID, int line)
    {
        var treeAsset = EditorUtility.InstanceIDToObject(instanceID) as TreeAsset;
        if (treeAsset == null) return false;
        OpenAsset(treeAsset);
        return true;
    }
    
    /// <summary>
    /// Open the editor and display the tree asset for editing.
    /// </summary>
    /// <param name="treeAsset"></param>
    public static void OpenAsset(TreeAsset treeAsset)
    {
        var wnd = GetWindow<TreeViewEditorExample>();
        wnd.titleContent = new GUIContent("TreeViewEditorExample");
        wnd.dataModel = treeAsset;
        wnd.treeView.SetRootItems(wnd.BuildNodeViews());
        wnd.Show();
    }

    public void CreateGUI()
    {
        treeView = new TreeView();
        
        //This is the key used to automatically save the state of the tree view (scroll position, selection, expanded items).
        //It should be unique for each editor window, if there are multiple editor window instances.
        treeView.viewDataKey = GetType().Name + "_TreeView";
        
        //makeItem constructs the visual element for each item in the tree view.
        treeView.makeItem = MakeTreeViewItem;
        
        //bindItem binds the data to the visual element created by makeItem.
        treeView.bindItem = BindTreeViewItem;
        treeView.unbindItem = UnbindItem;
        
        //There is no need to keep a list of TreeViewItems, as the tree view will manage them.
        treeView.SetRootItems(BuildNodeViews());
        
        //These are the events that are used to handle drag and drop.
        treeView.canStartDrag += OnCanStartDrag;
        treeView.setupDragAndDrop += OnSetupDragAndDrop;
        treeView.dragAndDropUpdate += OnDragAndDropUpdate;
        treeView.handleDrop += OnHandleDrop;
        
        //This is how cut, copy, paste and other editing commands are handled.
        treeView.RegisterCallback<ValidateCommandEvent>(OnValidateCommand);
        treeView.RegisterCallback<ExecuteCommandEvent>(OnExecuteCommand);
        
        //This is a button to rebuild the model data and the tree view.
        var rebuild = new Button(() =>
        {
            dataModel.Reset();
            treeView.SetRootItems(BuildNodeViews());
            treeView.Rebuild();
        });
        rebuild.text = "Rebuild";
        
        //This is a button to refresh the tree view to match the model.
        var refresh = new Button(() =>
        {
            treeView.SetRootItems(BuildNodeViews());
            treeView.Rebuild();
        });
        refresh.text = "Refresh";
        
        rootVisualElement.Add(rebuild);
        rootVisualElement.Add(refresh);
        rootVisualElement.Add(treeView);
        
        //This is how we handle undo and redo events.
        Undo.undoRedoPerformed -= UndoRedoPerformed;
        Undo.undoRedoPerformed += UndoRedoPerformed;
    }

    private void UndoRedoPerformed()
    {
        //Rebuild the tree view when undo or redo is performed.
        treeView.SetRootItems(BuildNodeViews());
        treeView.Rebuild();
    }

    //This callback method is called by the editor when a command is requested by the user.
    //A command is a request to perform an action, such as cut, copy, paste, delete, etc.
    private void OnExecuteCommand(ExecuteCommandEvent evt)
    {
        if (evt.commandName == "Copy")
        {
            //Copy the selected item to the clipboard.
            clipboardTree = dataModel.tree.CopySubtree((int)treeView.selectedItem);
        }
        if(evt.commandName == "Cut")
        {
            //Cut the selected item to the clipboard.
            clipboardTree = dataModel.tree.CopySubtree((int)treeView.selectedItem);
            //Remove the selected item from the data model.
            Undo.RecordObject(dataModel, "Cut Node");
            dataModel.tree.RemoveNode((int)treeView.selectedItem);
            treeView.SetRootItems(BuildNodeViews());
            treeView.Rebuild();
        }
        if(evt.commandName == "Paste")
        {
            Undo.RecordObject(dataModel, "Paste Node");
            dataModel.tree.AddSubtree((int)treeView.selectedItem, clipboardTree);
            treeView.SetRootItems(BuildNodeViews());
            treeView.Rebuild();
        }
        if(evt.commandName == "Duplicate")
        {
            var node = (int) treeView.selectedItem;
            var index = dataModel.tree.GetSiblingIndex(node);
            var parent = dataModel.tree.GetParent(node);
            Undo.RecordObject(dataModel, "Duplicate Node");
            dataModel.tree.AddSubtree(parent, dataModel.tree.CopySubtree(node), index);
            treeView.SetRootItems(BuildNodeViews());
            treeView.Rebuild();
        }
        if(evt.commandName == "SoftDelete")
        {
            Undo.RecordObject(dataModel, "Delete Node");
            dataModel.tree.RemoveNode((int)treeView.selectedItem);
            treeView.SetRootItems(BuildNodeViews());
            treeView.Rebuild();
        }
    }

    private void OnValidateCommand(ValidateCommandEvent evt)
    {
        if (evt.commandName == "Copy")
            evt.StopPropagation();
        if (evt.commandName == "Paste")
            evt.StopPropagation();
        if (evt.commandName == "Cut")
            evt.StopPropagation();
        if(evt.commandName == "Delete")
            evt.StopPropagation();
        if(evt.commandName == "Duplicate")
            evt.StopPropagation();
        if(evt.commandName == "SelectAll")
            evt.StopPropagation();
        if(evt.commandName == "SoftDelete")
            evt.StopPropagation();
    }


    private DragVisualMode OnHandleDrop(HandleDragAndDropArgs arg)
    {
        //This method is called when the drop operation is completed, by the user releasing the mouse button.
        //It is used to update the data model based on the drag operation.
        //Changes to the viewmodel happen automatically depending on the return value.
        //If we return DragVisualMode.None, the viewmodel will be updated. All other values will not update the viewmodel.
        
        //selectedIds is the ids of the items that are being dragged.
        var selectedIds = arg.dragAndDropData.GetGenericData("selectedIds") as IEnumerable<int>;
        
        Undo.RecordObject(dataModel, "Drag and Drop Node");
        
        //if arg.target is null, it means the drop is between items, and arg.parentId is the parent item of those items.
        //Therefore we need to insert the selected items at the specified arg.childIndex in the datamodel.
        if (arg.target == null)
        {
            //move the selected items to the new parent at childIndex
            foreach (var id in selectedIds)
            {
                dataModel.tree.AddChild(arg.parentId, id, arg.childIndex);    
            }
            return DragVisualMode.None;
        }
        else
        {
            //if arg.target is not null, arg.target is the id of the item that is being hovered over.
            //arg.target will be a DataModel.Node
            //append the selected items as children of the target
            foreach (var id in selectedIds)
            {
                dataModel.tree.AddChild(arg.parentId, id);    
            }
            return DragVisualMode.None;
        }
    }

    private DragVisualMode OnDragAndDropUpdate(HandleDragAndDropArgs arg)
    {
        //This method is used to determine if the drag operation is allowed.
        //It is called multiple times during the drag operation, when hovering over a tree item or between items.
        
        //targetId is the id of the item that is being hovered over.
        //If it is null, we are hovering between items, and arg.parentId is the parent item of those items.
        var targetId = (int) (arg.target ?? arg.parentId);
        //selectedIds is the ids of the items that are being dragged.
        //We can use this to determine if the drag operation is allowed.
        //In this example, we are not allowing moving a node to itself, creating another root node, or creating a circular reference.
        var selectedIds = arg.dragAndDropData.GetGenericData("selectedIds") as IEnumerable<int>;
        foreach (var id in selectedIds)
        {
            // Don't allow moving a node to itself
            if (id == targetId)
                return DragVisualMode.Rejected;
            // Allow creating another root node
            if(targetId < 0)
                return DragVisualMode.Copy;
            //is targetId we want to "move to" already a descendant of the selected item (id)? Then reject the move as it would create a circular reference.
            if(dataModel.tree.IsDescendantOf(targetId, id))
                return DragVisualMode.Rejected;
        }
        return DragVisualMode.Copy;
    }

    private StartDragArgs OnSetupDragAndDrop(SetupDragAndDropArgs arg)
    {
        //Inspect the arg and return the data needed for the drag operation.
        var startDragArgs = new StartDragArgs(arg.startDragArgs.title, DragVisualMode.Move);
        
        //selectedIds is the ids from the viewmodel that will be used in the drag operation.
        var selectedIds = arg.selectedIds;
        startDragArgs.SetGenericData("selectedIds", selectedIds);
        
        return startDragArgs;
    }

    private bool OnCanStartDrag(CanStartDragArgs arg)
    {
        //Inspect the arg and return true if the drag can start.
        return true;
    }

    private void BindTreeViewItem(VisualElement element, int index)
    {
        var label = element as Label;
        if (label == null) return;
        var viewmodelItem = treeView.GetItemDataForIndex<int>(index);
        label.text = dataModel.tree.GetData(viewmodelItem);
        label.userData = viewmodelItem;
        
    }
    
    private void UnbindItem(VisualElement element, int index)
    {
        element.userData = null;
    }


    private VisualElement MakeTreeViewItem()
    {
        var element = new Label();

        element.AddManipulator(new ContextualMenuManipulator((ContextualMenuPopulateEvent evt) =>
        {
            evt.menu.AppendAction("Add Child", (a) =>
            {
                var item = (int)treeView.selectedItem;
                Undo.RecordObject(dataModel, "Add Node");
                var newItem = dataModel.tree.CreateNode("Add Child");
                dataModel.tree.AddChild(item, newItem);
                var newViewModel = new TreeViewItemData<int>(newItem, newItem, new List<TreeViewItemData<int>>());
                treeView.AddItem(newViewModel, dataModel.tree.GetParent(newItem), dataModel.tree.GetSiblingIndex(newItem));
            });
            evt.menu.AppendAction("Delete", (a) =>
            {
                var item = (int)treeView.selectedItem;
                Undo.RecordObject(dataModel, "Delete Node");
                dataModel.tree.RemoveNode(item);
                treeView.TryRemoveItem(item, true);
            });
            evt.menu.AppendAction("Insert Sibling", (a) =>
            {
                //treeView.selectedItem;
                var item = (int)treeView.selectedItem;
                Undo.RecordObject(dataModel, "Insert Node");
                
                var parent = dataModel.tree.GetParent(item);
                var newItem = dataModel.tree.CreateNode("Insert Sibling", parentId:parent, index:dataModel.tree.GetSiblingIndex(item));
                var newViewModel = new TreeViewItemData<int>(newItem, newItem, new List<TreeViewItemData<int>>());
                treeView.AddItem(newViewModel, parent, dataModel.tree.GetSiblingIndex(newItem));
                
            });
        }));
        return element;
    }

    private List<TreeViewItemData<int>> BuildNodeViews()
    {
        if(dataModel == null)
            return new List<TreeViewItemData<int>>();
        
        List<TreeViewItemData<int>> GetNodeViews(int node)
        {
            var childViews = new List<TreeViewItemData<int>>();
            foreach (var child in dataModel.tree.GetChildren(node))
            {
                childViews.Add(new TreeViewItemData<int>(child, child, GetNodeViews(child)));
            }
            return childViews;
        }

        var rootViews = new List<TreeViewItemData<int>>();
        foreach (var rootNode in dataModel.tree.GetRoots())
        {
            rootViews.Add(new TreeViewItemData<int>(rootNode, rootNode, GetNodeViews(rootNode)));
        }

        return rootViews;
    }
    
}