CODEWITHSUNDEEP
pythonrecursionbinary-tree
Michael T
Michael T

Reputation: 45

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)

Upvotes: 1

Views: 986

Answers (2)

Ilja Everilä
Ilja Everilä

Reputation: 52939

In general when recursively working with binary trees you just have to handle the node at hand and recurse in to the children, if any. The "trick" is to treat the children, or the subbranches, as trees themselves. You also have to identify the edge condition which terminates the recursion.

Your current code will take the initial node, the root of your tree, increment the accumulator calc and recursively call do_calc for the rest of the tuple. This is different from recursing to the children. As the root node is a 3-tuple, recurse(tree) will return 3. The edge condition is the comparison with the empty tuple.

It seems that you want to count the nodes of the tree:

def tree_count(tree):
    # The edge condition: if a node is falsy (None, empty, what have you),
    # then terminate the recursion
    if not tree:
        return 0
    # Unpack the node, nicer to work with.
    value, left, right = tree
    # Count this node and recurse in to children.
    return 1 + tree_count(left) + tree_count(right)

If on the other hand your final goal would be to sum the values of the tree:

def tree_sum(tree):
    # The edge condition
    if not tree:
        return 0             
    value, left, right = tree
    # Sum this value and the values of children, if any
    return value + tree_sum(left) + tree_sum(right)

In case your actual tree is a k-ary tree or a just a tree with varying amounts of children per node:

def tree_sum(tree):
    if not tree:
        return 0
    # This still makes the assumption that the value is the 1st item of
    # a node tuple
    value, children = tree[0], tree[1:]
    # In python3:
    #value, *children = tree
    return value + sum(tree_sum(child) for child in children)

As mentioned the code makes the assumption that a node is a tuple with 1st element containing the value, like the example data provided. Without seeing the actual data it is somewhat impossible to do better. If it happens that your nodes are actually (left, value, right) tuples or so, modify accordingly.

Upvotes: 2

Lei Shi
Lei Shi

Reputation: 767

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.

Upvotes: 0

Related Questions