Michael T Michael T - 6 months ago 22
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)

Answer

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.

Comments