CODEWITHSUNDEEP
pythonalgorithmtreetraversal
CaseyJones
CaseyJones

Reputation: 505

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!

Upvotes: 1

Views: 576

Answers (2)

Sylvain Leroux
Sylvain Leroux

Reputation: 51990

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})})})

Upvotes: 2

Brionius
Brionius

Reputation: 14098

Here is a function that will recursively search for the "path" to a node - i.e. a list of parent nodes that locates the desired node:

def findNode(tree, findKey, nodeType):
    if type(tree) != nodeType:  # Check if this is another node or a leaf
        # Reached the end of a branch, and the key was not found, so:
        # return None in order to trigger a `TypeError` and reject this branch
        return None   
    for key in tree:
        if key == findKey:
            # Key was found - return the final part of the path
            return [key]
        else:
            try:
                # Search the next level in this branch
                return [key] + findNode(tree[key], findKey, nodeType)
            except TypeError:
                pass

Example usage:

from collections import defaultdict
def Tree():
    return defaultdict(Tree)
t = Tree()

t[1][2][3][4] = 99
t[1][2][7][9] = 101
t[1][10][19][22] = 44
t[1][10][19][77] = 2822

findNode(t, 22, type(t))
# Result:
# [1, 10, 19, 22]

findNode(t, 7, type(t))
# Result:
# [1, 2, 7]

Upvotes: 2

Related Questions