Counting leaves with Python

If you have a multi-level dictionary in python looking like:

tree = {
    "first1": {
        "second1": {
            "third1": {
                "leaf1": 123,
                "leaf2": 234,
                "leaf3": 345
            }
        },
        "second2": {
            "leaf4": 456,
            "leaf5": 567
        }
    },
    "leaf6": 678
}

Here's a way to recursively count the number of elements, or "leaves" in this so-called dictionary tree (a single leaf being anything that's not a dictionary):

def leafcounter(node):
    if isinstance(node, dict):
        return sum([leafcounter(node[n]) for n in node])
    else:
        return 1
leafcounter(tree) # returns 6

You can also do it with a lambda instead of an actual method:

leafcounter = lambda val: sum(
    [leafcounter(val[n]) for n in val]
) if isinstance(val, dict) else 1
leafcounter(tree) # returns 6

And last but not least, you can also do it all in one line of code with an unnamed recursive lambda (using the answer found here for reference on unnamed recursive lambdas) though, as you can see, it gets pretty ugly:

sum(
    map(
        lambda g: (
            lambda f, *a: f(f, *a)
        )(
            lambda rec, val: sum(
                [rec(rec, val[n]) for n in val]
            ) if isinstance(val, dict) else 1, g
        ), tree.itervalues()
    )
)
# returns 6

Posted Wed 03 August 2011 by Ivan Dyedov in Python (Python)