how to traverse this tree?

I've come across this python trick of creating a tree:

def Tree():
    return defaultdict(Tree)

t = Tree()
t["key1"]["key2"]["key3"] = value

So I'm using it in such a way that each key in this data structure is unique regardless of which dimension I am at. However, this poses a bit of a problem as I want to be able to insert new keys based on a specific parent, e.g I want to insert a child to key3, how do I traverse it in such a way that it finds key3? What strategies/approaches can I take to find a given "key" for example?

I have a feeling this can be solved recursively, but I'm fairly inexperienced with recursion and programming and this is my first attempt at solving a group of groups type problem. Thanks!

Solution

I choose here to find the relevant node using that simple recursive function:

def find(t, search):
    #
    # Find the *first* dictionary object having
    # the key "search"
    for k in t:
        if k == search:
            return t
        if isinstance(t[k],dict):
            result = find(t[k],search)
            if result:
                return result

    return None

Once you get the node, you might change it as you want:

>>> from pprint import pprint
>>> pprint(t)
defaultdict(<function Tree at 0x1c17488>, {
  'key1': defaultdict(<function Tree at 0x1c17488>, {
            'key2': defaultdict(<function Tree at 0x1c17488>, {
                      'key3': 99})})})


>>> node = find(t, "key3")
>>> pprint(node)
defaultdict(<function Tree at 0x1c17488>, {
  'key3': 99})

As you now have a reference to the newly found dictionary, changing it through that reference will alter the "original" tree -- as both contains references to the same object. I'm not quite clear, so look at this example:

>>> node["key3b"]=0
>>> pprint(t)
defaultdict(<function Tree at 0x1c17488>, {
  'key1': defaultdict(<function Tree at 0x1c17488>, {
            'key2': defaultdict(<function Tree at 0x1c17488>, {
                      'key3': 99, 
                      'key3b': 0})})})