Iterate through a Nested Python Dictionary?

Question

I am trying to iterate through a multi-level, and varied-level dictionary. I have an org char (dictionary) with the keys as people names, and values as either None or a dictionary with another org chart.

If the name has any values other than None they're a "leader", otherwise, they're "non-leader". Every first-level dictionary names are the leader's direct reports, and further through the nested dictionaries are the leader's indirect reports.

Given a name (string) and an org_chart (nested dictionary), I'd like to implement a function lookup_info, that outputs whether the name is a "leader" or "non-leader", how many direct reports they have, and how many indirect reports they have.

I'm not new to Python, but I'm stuck at the traversing (is this BFS or DFS) and how to use recursion here.

Here's an example:

ORG_CHART = {

"chloe" : {
        "mark" : {
            "tim" : {
                "varun" : None,
                "misha" : None
                }
            },
        "julie" : None
        },
"annie" : {
        "jimmy" : {
            "haily" : None,
            "alex" : None
        },
        "helen" : {
            "miley" : {
                "stella" : {
                    "allie" : None
                },
                "tom" : None
            }
        }
},
"jenny" : None
}

def lookup(name, org_chart):
#TODO
return leadership_type, num_direct_reports, num_total_reports

name = "annie" should output: "leader", 2, 8 because annie has people reporting to her so she's a leader. She has 2 people directly in her values dict, so 2 direct reports, and 8 total people working under her.

name = "tom" should output: "non-leader", 0, 0

name = "miley" should output "leader", 2, 3

I've tried the following to recurse the nested dictionaries (not actually getting any info yet, but just trying to find the values in the dictionaries first, because the counting is the next step), but I'm stuck at this very first step. It's returning None of course if it hits any level above the first level that doesn't have a dictionary as it's values.

def lookup_info(name, org_chart):

    def get_name_value(name, org_chart):
        if org_chart != None:
            for k, v in org_chart.items():
                if k == name:
                    return k
                else:
                    if v != None:
                        for i, j in v.items():
                            get_name_value(name, j)

    name = get_name_value(name, org_chart)

    return name

Any ideas please let me know, thank you!

Answer 1

Recursion is a bit tricky to wrap the brain around, so here is a more verbose option which takes a naïve step-by-step through the process in a human readable manner.

Note that this does not account for duplicates or other edge cases and is certainly neither the shortest or most efficient method, but I think it should serve you well as a good jumping off point.

def lookup_info(name, org_chart):
    # some local variables to hold our results
    leadership_type = None
    num_direct_reports = 0
    num_total_reports = 0

    def helper(obj, depth):
        # declare our intent to use the variables from above as nonlocals
        nonlocal leadership_type, num_direct_reports, num_total_reports

        # if the value is None, we hit a leaf and should return
        if obj is None:
            return

        # otherwise, iterate through the key value pairs
        for key, value in obj.items():
            # if we see the name in the keys, we proceed accordingly
            if key == name:
                if value is not None:
                    # mark as a leader, and recurse with increased depth noted in param
                    leadership_type = "leader"
                    helper(obj=value, depth=depth + 1)
                else:
                    # otherwise this is a non-leader, we can return
                    leadership_type = "non-leader"
                    return
            elif depth == 1:
                # at depth 1 we handle direct subordinates, and recurse
                num_direct_reports += 1
                num_total_reports += 1
                helper(obj=value, depth=depth + 1)
            elif depth > 1:
                # at depth > 1 we handle indirect subordinates, and recurse
                num_total_reports += 1
                helper(obj=value, depth=depth + 1)
            else:
                # here we continue checking deeper into the structure to cover all other cases from depth 0
                helper(obj=value, depth=0)

    # run our helper with the appropriate defaults to start
    helper(obj=org_chart, depth=0)

    # finally return the thruple
    return leadership_type, num_direct_reports, num_total_reports