Michael T - 1 year ago 68
Python Question

recursively parse all of the levels of tree

What is the best way to recursively parse all of the levels of this tree structure. The three levels are first but how should it proceed to parse the remaining data? This is from a codility test that I couldn't complete. There was more to the question, but this is where I got stuck.

``````tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None)))

def recurse(T):
calc = 0
def do_calc(T, calc):
if T == ():
return calc
calc += 1
return do_calc(T[1:], calc)
return do_calc(T, calc)

print recurse(tree)
``````

It looks like you want to get the depth of the tree. Here is the typical solution with recursion:

``````tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None)))

def tree_depth(node):

if not isinstance(node, tuple):
return 1
else:
return max(tree_depth(subnode) for subnode in node) + 1

print tree_depth(tree)
``````

The output is 5.

Built in function max and generator expression are used in the sample code.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download