I Have A Recursive Function To Validate Tree Graph And Need A Return Condition

I have a tree graph. Each node has attribute 'amount'. The rule governing the attribute value of root is this, The root 'amount' value is the sum of the 'amount' attribute of each

Solution 1:

To report the final result, you could combine the validate results of subtrees and current node, so the recursive procedure will look like: How to collect and record results depends on the situation, there are some options:

1. construct the result recursively
2. use a global variable to record
3. result raise an exception

Example 1

And example for constructing result recursively, here the function return a boolean value and combines result of children by logical and:

def validate(G, node):
    if isLeaf(G, node): # This is the base case  
        return True
    else:
        # step 1
        validate_results_of_children = [validate(G, child) for child in G.successors(node)]

        # step 2
        is_current_node_valid = check_current_node_sum(G, node)

        # step 3
        final_result = all(validate_results_of_children) and is_current_node_valid 

        return final_result

Example 2

Use a global dict to record invalid results and add some extra info about tree level:

def validate(G, node, record_dict, tree_level):
    if isLeaf(G, node):  # This is the base case
        pass
    else:
        # step 1
        for child in G.successors(node):
            validate(G, child, record_dict, tree_level + 1)

        # step 2
        is_current_node_valid = check_current_node_sum(G, node)

        # step 3
        record_dict.setdefault(tree_level, {})
        record_dict[tree_level][node] = is_current_node_valid

record_dict = {}
validate(G, root, record_dict, tree_level=0)

Example 3

Define a custom exception class and raise it when tree is not valid: class TreeNotValidException(Exception): pass

def validate(G, node):
    if isLeaf(G, node):  # This is the base case
        pass
    else:
        # step 1
        for child in G.successors(node):
            validate(G, child, tree_level + 1)

        # step 2
        is_current_node_valid = check_current_node_sum(G, node)

        # step 3
        if not is_current_node_valid:
            raise TreeNotValidException("Invalid sum for node : " + node)