Aggregating values of nodes over a tree

Question

I have a rather complex tree structure that I want to traverse and aggregate values over (e.g. sum, concatenate, append...). I want traverse to be a method of the tree rather than a separate function. I can traverse and apply a function to each node, but I cannot figure out how to update an aggregation variable associated with the tree.

Here is a simplified version of my code including a node handler with no aggregation, this works.

# A tree is a node that recursively includes more nodes under it.
# More correctly the Tree is the particular node regarded as the root Node.
class Node:
    def __init__(self, value):
        self.value = value
        self.children = []
    def traverse(self, handle_node):
        handle_node(self)
        for child in self.children:
            child.traverse(handle_node)

tree = Node('A')
tree.children.append(Node('B')) # Note we append Nodes not values!
tree.children.append(Node('C'))
tree.children[1].children.append(Node('D'))
tree.children[1].children.append(Node('E'))

# This is just an example of a node-handler.
def example_func_on_a_node(node):
    print(node.value)

# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node)

As expected this prints

A
B
C
D
E

However, what I want is to aggregate in the general case. If I have a node-handler that returns a value how can I combine the value from each node with the values from all prior nodes to ultimately return the aggregate. The node-handler needs to be a general function that takes a node as it's argument and returns a value.

For example suppose I wanted to concatenate the values in the above simple example. The code should look something like this, but this does not work.

class Node2:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.concat = ''
    def traverse(self, handle_node):
        self.concat += handle_node(self)
        for child in self.children:
            child.traverse(handle_node)

tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))

# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
     return node.value

# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(tree.concat)

The answer I get is A, but what I want is 'ABCDE'

Note I have tried many variations including using static and class methods, and nonlocal variables, but quite possibly used them incorrectly.

I can sort of see what I need but cannot see where to place the aggregation variable so it gets passed around the tree and back to the root node while keeping the node-handler and Node class simple.

finefoot · Accepted Answer · 2019-12-29T03:13:53.477

Your code doesn't work, because self.concat refers to the current node. So you don't aggregate the values somewhere but you put the value of each node into a separate concat variable and eventually only print one of them (the first one). So what you need to do is to provide a reference to the same variable for each call of traverse. There are various ways to do this:

Possibility A: Use a global variable (Also, see Why are global variables evil?)

class Node2:
    def __init__(self, value):
        self.value = value
        self.children = []
    def traverse(self, handle_node):
        global concat
        concat += handle_node(self)
        for child in self.children:
            child.traverse(handle_node)

concat = ''
tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))

# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
     return node.value

# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(concat)

Possibility B: Use a class variable

class Node2:
    concat = ''
    def __init__(self, value):
        self.value = value
        self.children = []
    def traverse(self, handle_node):
        self.__class__.concat += handle_node(self)
        for child in self.children:
            child.traverse(handle_node)

tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))

# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
     return node.value

# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(tree.concat)

Possibility C: Use return in traverse to "relay" the inner concat values to the first one

class Node2:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.concat = ''
    def traverse(self, handle_node):
        self.concat += handle_node(self)
        for child in self.children:
            self.concat += child.traverse(handle_node)
        return self.concat

tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))

# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
     return node.value

# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(tree.concat)

Possibility D: Add an optional argument to traverse to pass a reference to the first node into subsequent calls to traverse

class Node2:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.concat = ''
    def traverse(self, handle_node, tree=None):
        if tree is None:
            tree = self
        tree.concat += handle_node(self)
        for child in self.children:
            child.traverse(handle_node, tree)

tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))

# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
     return node.value

# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(tree.concat)

Thanks, brilliant, option B will work best for my particular use case, but I will try C and D as well. For my use case example_func_on_a_node2 can be a method of Node2 (not shown in simplified problem). — Mark Kortink, Dec 30 '19 at 10:38
Actually option C is best for my use case as under option B there could be contention on the class variable. Option C generalised my requirements nicely because I can collect the returned values into a list or dictionary then aggregate them any which way. — Mark Kortink, Dec 30 '19 at 21:32

Aggregating values of nodes over a tree

1 Answers1