def sum(root):
if root.children == []:
return root.value
else:
temp = 0
for n in root.children:
temp += sum(n)
temp+= root.value
return temp
I got my function to work recursively and am trying to figure out an easy way to do it iteratively. I just am trying to find guidance as to if I would be using a while loop or what.
Use a queue or stack; take an element from your queue or stack, add the value to the running total, add any children to the queue or stack, then process the next element. Use a while loop that ends when your queue or stack is empty.
The only difference between a stack and a queue is that you'll either process your elements depth first (stack) or breath first (queue).
Your recursive code is depth-first, so to replicate the same behaviour iteratively, use a stack:
def sum_nodes_iteratively(root):
elements = [root]
total = 0
while elements:
element = elements.pop()
elements.extend(element.children)
total += element.value
return total
Demo:
>>> class Node(object):
... def __init__(self, value, children):
... self.value = value
... self.children = children
...
>>> def sum_nodes_iteratively(root):
... elements = [root]
... total = 0
... while elements:
... element = elements.pop()
... elements.extend(element.children)
... total += element.value
... return total
...
>>> sum_nodes_iteratively(Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])]))
28
