Question: In the following binary tree, only leaves hold values, no internal nodes hold values. I implemented traversing (to calculate the sum of values leaves hold) using **recursion**:

```
class Node:
    def new(rep):
        if type(rep) is list:
            left = Node.new(rep[0])
            right = Node.new(rep[1])
            return Internal(left, right)
        else:
            return Leaf(rep)

class Leaf(Node):
    def __init__(self, val):
        self.val = val

    def sum_leaves(self, sum):
        return sum + self.val

class Internal(Node):
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def sum_leaves(self, sum):
        return self.right.sum_leaves(self.left.sum_leaves(sum))

class Tree:
    def __init__(self, rep):
        self.root = Node.new(rep)

    # Traverse the tree and return the sum of all leaves
    def sum_leaves(self):
        return self.root.sum_leaves(0)

treerep = [[3, [5, -1]], [[1, 7], [2, [3, [11, -9]]]]]
tree = Tree(treerep)
print(tree.sum_leaves())

```

The output in this case is:

```
22

```

How can I use **iteration** instead of recursion for `sum_leaves` method?

Answer: 
You can use Depth First Search which uses a while loop:

```
class Tree:
    def __init__(self, rep):
        self.root = Node.new(rep)

    def sum_dfs(self):

        sum = 0
        stack = [self.root]

        while len(stack):

            node = stack.pop()

            if isinstance(node, Internal):
                stack.append(node.left)
                stack.append(node.right)

            elif isinstance(node, Leaf):
                sum += node.val

        return sum

```
you can even try tricks.

```
import re

treerep = [[3, [5, -1]], [[1, 7], [2, [3, [11, -9]]]]]

p = re.compile('(\[|\]|,)')
treerep = p.sub('', str(treerep))
treerep = [int(i) for i in treerep.split()]

sum(treerep)

```

easy))