Finding the bottom folders of a file tree using PowerShell

There’s a simple way of getting Powershell to tell you the last folder in a known path:

$path = \\server\share\folder1\folder2\folder3
$folder = Split-Path $path -Leaf

and that’s all you need.

Now, how do you go about doing that if you don’t know the path ahead of time? That is, you have a large collection of directories, and all you want are those folders than make up the bottom levels of the branches. In this graphic it would be all the folders underlined.

As an example, current $EMPLOYER holds backups from all SQL databases on a share, with each database’s backups being in a folder. Due to various DBAs over the years the depth of the tree to the actual backups isn’t fixed. So I need to find the “bottom” folder so I can process the backup files in there.

Well, that’s a little trickier. So lets have a look at a couple of ways of doing that:

First of all let’s get ourselves a nice object containing all the potential directories:

$dirs = Get-ChildItem "\\server1\backups$" -Recurse -Directory

On my test subject, this contains 2233 directory objects of varying depths. I’ve pulled this out here so that I can compare the speed of the 3 approaches without this operation clouding anything.

The first option is based on looping through out $dirs object, calling Get-Childitem -Directory on each folder, and by definition a folder at the bottom of the tree will have no child directories so we check for that condition. Each time we find a folder with no child folders we add the path to a $children array:

$children1 = New-Object System.Collections.ArrayList
$time1start = get-date
foreach ($d in $dirs){
    if ((Get-ChildItem $d.fullname -Directory).count -eq 0){
        $children1.add($d.FullName)
    }
}
$time1finish = get-date
$time1taken = $t1f - $t2f
$count1 =  $children1.count

I’m wrapping each sample in a little bit of timing code so we can compare performance. In this case this routine takes 45.93 seconds against my test data, returning 1750 leaf folders.

Now, can we improve on that a little? Yes, we can. Version 1 requires an extra Get-ChildItem call for each folder, so in this case that’s an extra 2233 calls. Luckily for us, each DirectoryInfo object has a EnumerateDirectories method we can use, which is implemented at a lower level and saves calling another cmdlet:

$children2 = New-Object System.Collections.ArrayList

$time2start = get-date
foreach ($d in $dirs){
    if (($d.EnumerateDirectories()).count -eq $NULL){
        $children2.add($d.fullname)
    }
}
$time2finish = get-date
$time2taken = $time2finish-$time2start
$count2 = $children2.count

Since there are no child directories for a leaf folder EnumerateDirectories returns NULL rather than 0, which is why we have to check for that.

This approach returns the same number of leaf folders as the first, 1750. But this time it only took 26.48 seconds. Not too shabby an improvement I think you’d agree.

Being an inveterate tinkerer, I wondered if there was an even quicker way, one that doesn’t need to refer to the filesystem once we’ve populated $dir. And there is:

$children3 = New-Object System.Collections.ArrayList
$time3start = get-date
foreach ($d in $dirs){
    $t = split-path $d.FullName -Parent
    if ($children3 -notcontains $t){
        $children3.add($d.fullname)
    }else{
        $children3.remove($t)
        $children3.add($d.fullname)
    }
}
$time3finish = get-date
time3taken = $time3finish - $time3start
$count3 = $children3.count

We loop through each item in $dir as before, we use Split-Path to get the parent folder of the folder we’re currently looking at, then we take 1 of 2 steps:

• If the parent folder doesn’t already exist in $children, then we add the full path to $children
• If the parent folder does exist in $children, then we know it must have child folders, so we remove it and replace it with the full path

This method returns the same list of bottom folders. But, this time it took 1.9 seconds, which is a huge improvement over our first model.

As if often shown whenever you’re programming or writing scripts:

• Avoid calling any extra commands, as there will be a price to pay
• If you must call an extra method, use the most efficient one you can find
• Working with the data you’ve already got is usually going to be the fastest way to do something
• Extra calls to the filesystem are always slow

And if anyone has any strong opinions over what you’d call the folder at the bottom of a filesystem tree (bottom folder?, leaf folder?, last folder?, anti-root folder?) then please let me know!