flat list to hierarchy

Question

I'm having the hardest time converting a list(Of Folder) into a hierarchy.

Public Class Folder

Public Property FolderID() As Integer
Public Property Name() As String
Public Property ParentFolderID() As Integer
Public Property Children() as IEnumerable(Of Folder)

End Class

I need to return List(Of Folder) with Children populated.

I build a List(Of Folder) from the data in the database.

{1, "Folder 1", Nothing} {2, "Folder 2", 1} {3, "Folder 3", 2} {4, "Folder 4", 3} {5, "Folder 5", Nothing}

I can't figure out how to recursively move the child folders into the Children property of their parent.

I would like to do this with LINQ.

Any help is greatly appreciated.

Update

Thank you for your answer, but not quite there. Based on your answer, I came up with this which almost works.

Dim list = (From folder in folderList Select New Folder() With {
    .FolderID = folder.FolderID, 
    .Name = folder.Name, 
    .ParentFolderID = folder.ParentFolderID, 
    .Children = (From child in folderList 
                 Where child.ParentFolderID = item.FolderID).ToList()}).ToList()

{1, "Root", Nothing}
{2, "Child", 1}
{3, "Grand Child", 2}

I get a list of all three folders:

Root
--Child
Child
--Grand Child
Grand Child

Should look like:

Root
--Child
----Grand Child

Answer 1

It's easy if you use the ToLookup extension method.

C#:

var lookup = folderList.ToLookup(f => f.ParentFolderID);

foreach (var folder in folderList)
{
    folder.Children = lookup[folder.FolderID].ToList();
}

var rootFolders = lookup[null].ToList();

VB:

Dim lookup = folderList.ToLookup(Function (f) f.ParentFolderID)

For Each folder In folderList
    folder.Children = lookup(folder.FolderID).ToList()
Next

Dim rootFolders = lookup(Nothing).ToList()