Public Property Set Root(ByVal Value As TreeNode)
    Set this.Root = Value
End Property

Private Sub Class_Initialize()
    Set this.Root = New TreeNode
End Sub

Why do you need to expose a setter at all? As soon as you create a new Tree, you're ready to add child nodes using myTree.Root.Children.

This brings me to this superfluous test here:

'@TestMethod
Public Sub RootIsNotNothingAfterSetting()
    'Arrange:
    Set t = New Tree

    'Act:
    Set t.Root = New TreeNode

    'Assert
    Assert.IsNotNothing t.Root
End Sub

You're already testing that Root is set upon tree creation; what the setter is allowing, really, is for weirdness like this:

Set myTree.Root = Nothing

Which defeats the test and highlights that your data structure is missing an important [tiny little] detail: immutability!

No one should ever be allowed to swap that Root reference! If client code needs a new Root, then they need a new Tree!

Public Sub ParentIsNotNothingAfterRemovingChild() 'TODO: Rename test

That test was definitely renamed, and yet you still have a TODO item here that could be removed.

'@TestInitialize
Public Sub TestInitialize()
    Set t = New Tree
    t.Root.Name = "C:"
End Sub

'@TestCleanup
Public Sub TestCleanup()
    Set t = Nothing
End Sub

The Rubberduck setup & teardown methods don't need @TestInitialize and @TestCleanup markers if they're named [respectively] TestInitialize and TestCleanup - I only know because I wrote the framework though :)

These markers exist in the event where one would like to use different names for setup & teardown. Note that this is also the reason why TestInitialize and TestCleanup cannot be used as test method names without a @TestMethod marker.

Public Property Set Root(ByVal Value As TreeNode)
    Set this.Root = Value
End Property

Private Sub Class_Initialize()
    Set this.Root = New TreeNode
End Sub

Why do you need to expose a setter at all? As soon as you create a new Tree, you're ready to add child nodes using myTree.Root.Children.

This brings me to this superfluous test here:

'@TestMethod
Public Sub RootIsNotNothingAfterSetting()
    'Arrange:
    Set t = New Tree

    'Act:
    Set t.Root = New TreeNode

    'Assert
    Assert.IsNotNothing t.Root
End Sub

You're already testing that Root is set upon tree creation; what the setter is allowing, really, is for weirdness like this:

Set myTree.Root = Nothing

Which defeats the test and highlights that your data structure is missing an important [tiny little] detail: immutability!

No one should ever be allowed to swap that Root reference! If client code needs a new Root, then they need a new Tree!

Public Sub ParentIsNotNothingAfterRemovingChild() 'TODO: Rename test

That test was definitely renamed, and yet you still have a TODO item here that could be removed.

'@TestInitialize
Public Sub TestInitialize()
    Set t = New Tree
    t.Root.Name = "C:"
End Sub

'@TestCleanup
Public Sub TestCleanup()
    Set t = Nothing
End Sub

The Rubberduck setup & teardown methods don't need @TestInitialize and @TestCleanup markers if they're named [respectively] TestInitialize and TestCleanup - I only know because I wrote the framework though :)

These markers exist in the event where one would like to use different names for setup & teardown. Note that this is also the reason why TestInitialize and TestCleanup cannot be used as test method names without a @TestMethod marker*.

_{* actually that's not exactly true - see issue #329 - "@TestMethod" marker has no effect on a method named "TestInitialize" or "TestCleanup"}