use strict;
use warnings;
use Data::Dump::Streamer;

my $branch1 = {
    Leaves => [qw(Leaf1 Leaf2)],
    Branch2 => {
        Leaves => [qw(Leaf3)],
        Branch3 => {
            Leaves => [qw(Leaf4 Leaf5)],
            Branch4 => {
                Leaves => [qw(Leaf6)],
                }
            }
        },
    Branch5 => {
        Leaves => [qw(Leaf7)],
        Branch6 => {
            Leaves => [qw(Leaf8 Leaf9)],
            }
        },  
    };

print "Original Tree:\n";
Dump ($branch1);
removeBranch ($branch1);
print "New Tree:\n";
Dump ($branch1);


sub removeBranch {
    my ($root, $branch) = @_;
    my $leafKey;
    my $keep;

    $branch = $root unless $branch;

    for my $child (keys %$branch) {
        if ('ARRAY' eq ref $branch->{$child}) {
            $leafKey = $child;
            next;
        }

        if (removeBranch ($root, $branch->{$child})) {
            delete $branch->{$child};
        } else {
            $keep = 1;
        }
    }

    return ! $keep unless $leafKey;
    
    my $leaves = $branch->{$leafKey};
    return undef if @$leaves > 1; # Leave this branch alone

    push @{$root->{Leaves}}, @$leaves;
    delete $branch->{$leafKey};
    return ! $keep;
}


__DATA__
Branch1 (Leaf1 Leaf2)
    Branch2 (Leaf3)
        Branch3 (Leaf4 Leaf5)
            Branch4 (Leaf6)
    Branch5 (Leaf7)
        Branch6 (Leaf8 Leaf9)
    
Branch1 (Leaf1 Leaf2 Leaf3 Leaf6 Leaf7)
    Branch3 (Leaf4 Leaf5)