private void CheckItemCommand_Executed(IFooViewModel changedItem)
{
    var items = TreeLib.BreadthFirst.Traverse.LevelOrder
                  <IFooViewModel>(changedItem.Children, i => i.Children);

    // All children of the checked/unchecked item have to assume it's state
    foreach (var item in items)
    {
        var node = item.Node as FooViewModel;
        node.IsChecked = changedItem.IsChecked;
    }
    
    // Visit each parent in turn and determine their correct states
    var parentItem = changedItem.Parent;
    
    for( ; parentItem != null; parentItem = parentItem.Parent)
    {
      ResetParentItemState(parentItem as IFooViewModel);
    }
}

private void ResetParentItemState(IFooViewModel item)
{
    if (item == null)
      return;
    
    if (item.ChildrenCount == 0)
      return;

    var itemChildren = item.Children.ToArray();

    bool? firstChild = itemChildren[0].IsChecked;
    
    for(int i=1; i< itemChildren.Length; i++)
    {
      if (Object.Equals(firstChild, itemChildren[i].IsChecked) == false)
      {
        // Two different child states found for this parent item ...
        item.IsChecked = null;
        return;
      }
    }
    
    // All child items have the same state as the first child
    item.IsChecked = firstChild;
}

Private Sub CheckItemCommand_Executed(ChangedItem As IFooViewModel)
    Dim items = TreeLib.BreadthFirst.Traverse.LevelOrder(Of IFooViewModel)(ChangedItem.Children, Function(i) i.Children)

    '' All children of the checked/unchecked item have to assume it's state
    For Each item In items
        Dim node = TryCast(item.Node, FooViewModel)
        node.IsChecked = ChangedItem.IsChecked
    Next

    '' Visit each parent in turn And determine their correct states
    Dim parentItem = ChangedItem.Parent

    While parentItem IsNot Nothing
        ResetParentItemState(TryCast(parentItem, IFooViewModel))

        parentItem = parentItem.Parent
    End While
End Sub

Private Sub ResetParentItemState(item As IFooViewModel)

    If (item Is Nothing) Then
        Return
    End If

    If item.ChildrenCount = 0 Then
        Return
    End If

    Dim itemChildren = item.Children.ToArray()

    Dim firstChild As Boolean?
    firstChild = itemChildren(0).IsChecked

    For i = 0 To itemChildren.Length - 1
        If (Object.Equals(firstChild, itemChildren(i).IsChecked) = False) Then

            '' Two different child states found for this parent item ...
            item.IsChecked = Nothing
            Return
        End If
    Next

    '' All child items have the same state as the first child
    item.IsChecked = firstChild
End Sub