Traversing binary tree using iteration instead of recursion in Python

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:

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

What do you exactly mean with iteration? Every iteration increases the depth level or? — ToTheMax
– ToTheMax, Commented Apr 6, 2020 at 21:29

ToTheMax · Accepted Answer · 2020-04-06 21:52:04Z

4

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

answered Apr 6, 2020 at 21:52

ToTheMax

1,02111 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kholdarbekov · Accepted Answer · 2020-12-15 06:00:31Z

2

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))

edited Dec 15, 2020 at 6:00

answered Dec 15, 2020 at 5:48

Kholdarbekov

1,1652 gold badges12 silver badges28 bronze badges

1 Comment

Muhammadjon Over a year ago

Sorry, it isn't what I wanted:)

Alain T. · Accepted Answer · 2020-04-10 22:28:37Z

The deque object from collections is very efficient to implement a "manual" stack and can help with this kind of traversal. I would suggest defining an iterator method that will traverse the hierarchy using a loop (and deque) and then using that method to implement the sum_leaves() method.

from collections import deque

def traverse(self,condition=None): # on the Node class
    nodes = deque([self])
    while nodes:
        node = nodes.popleft()
        if not condition or condition(node): yield node
        if node.isLeaf: continue
        if node.left:  nodes.append(node.left)
        if node.right: nodes.append(node.right)

@property
def isLeaf(self): isinstance(self,Leaf)  # on the Node class

def sum_leaves(self): # on the Node class
    return sum(n.val for n in self.traverse(lambda n:n.isLeaf))

def sum_leaves(self): # on the Tree class
    return self.root.sum_leaves()

I believe that there would be a lot fewer exceptions in the code if you didn't separate the tree structure in 3 incompatible classes. All nodes (including the Tree which should itself be the root) should be able to have a left, right and value property (at least at the signature level).

Collectives™ on Stack Overflow

Traversing binary tree using iteration instead of recursion in Python

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related