how to traverse this tree?

Question

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!

What would you do with the value that is stored under "key3"? You're turning a leaf into a node - would you just get rid of value? — Brionius
– Brionius, Commented Sep 1, 2014 at 16:48
I'm not sure I understood your question, apologies, but if I understood you correctly, the value would be a value to key3,e.g a non-empty dict — CaseyJones
– CaseyJones, Commented Sep 1, 2014 at 16:56
Never mind - I answered your question in a different way so my question is irrelevant. — Brionius
– Brionius, Commented Sep 1, 2014 at 17:22

Sylvain Leroux · Accepted Answer · 2014-09-01 17:50:29Z

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

Brionius · Accepted Answer · 2014-09-01 17:22:17Z

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]

Collectives™ on Stack Overflow

how to traverse this tree?

2 Answers 2

Comments

Example usage:

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Example usage:

Comments

Related