CODEWITHSUNDEEP
pythonalgorithmiterationbinary-tree
Alex Helvaty
Alex Helvaty

Reputation: 57

Sum of all Nodes Iteratively - Not Recursively - Without 'left' and 'right'

I have this Binary Tree Structure:

# A Node is an object
# - value : Number
# - children : List of Nodes
class Node:
    def __init__(self, value, children):
        self.value = value
        self.children = children

I can easily sum the Nodes, recursively:

def sumNodesRec(root):
    sumOfNodes = 0
    for child in root.children:
        sumOfNodes += sumNodesRec(child)
    return root.value + sumOfNodes

Example Tree:

exampleTree = Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])

sumNodesRec(exampleTree)

> 28

However, I'm having difficulty figuring out how to sum all the nodes iteratively. Normally, with a binary tree that has 'left' and 'right' in the definition, I can find the sum. But, this definition is tripping me up a bit when thinking about it iteratively.

Any help or explanation would be great. I'm trying to make sure I'm not always doing things recursively, so I'm trying to practice creating normally recursive functions as iterative types, instead.

Upvotes: 2

Views: 1785

Answers (3)

cs95
cs95

Reputation: 402263

If we're talking iteration, this is a good use case for a queue.

total = 0

queue = [exampleTree]
while queue: 
    v = queue.pop(0)
    queue.extend(v.children)
    total += v.value

print(total)
28

This is a common idiom. Iterative graph traversal algorithms also work in this manner.

You can simulate stacks/queues using python's vanilla lists. Other (better) alternatives would be the collections.deque structure in the standard library. I should explicitly mention that its enque/deque operations are more efficient than what you'd expect from a vanilla list.

Upvotes: 6

Alex Helvaty
Alex Helvaty

Reputation: 57

In response to the first answer: 

def sumNodes(root):
    current = [root]
    nodeList = []
    while current:
        next_level = []
        for n in current:
            nodeList.append(n.value)
            next_level.extend(n.children)
        current = next_level
    return sum(nodeList)

Thank you! That explanation helped me think through it more clearly.

Upvotes: 2

Sami Kuhmonen
Sami Kuhmonen

Reputation: 31143

Iteratively you can create a list, stack, queue, or other structure that can hold the items you run through. Put the root into it. Start going through the list, take an element and add its children into the list also. Add the value to the sum. Take next element and repeat. This way there’s no recursion but performance and memory usage may be worse.

Upvotes: 2

Related Questions