CODEWITHSUNDEEP
pythonpython-3.x
cheese00
cheese00

Reputation: 27

how to iteratively present a preorder (binary tree)?

my code:

class BinaryTree:
    def __init__(self, key):
        self.key = key
        self.left_child = None
        self.right_child = None

    (...)

    def __str__(self):
        return "[{}; {}; {}]".format(self.key, self.left_child, self.right_child)

    def preorder(self): # recursively
        print(self.key)

        if self.left_child:
            self.left_child.preorder()
        if self.right_child:
            self.right_child.preorder()

but I don't know how to write iterative code.

I would like the code to return an iterator in the form of a node.

Upvotes: 0

Views: 50

Answers (1)

Booboo
Booboo

Reputation: 44053

The iterative solution needs to use a stack to remember the nodes that it needs to traverse while the recursive solution implicitly uses a stack, i.e. the return stack of function calls:

class BinaryTree:
    def __init__(self, key):
        self.key = key
        self.left_child = None
        self.right_child = None

    def __str__(self):
        return "[{}; {}; {}]".format(self.key, self.left_child, self.right_child)

    def preorder_recursive(self): # recursively
        print(self.key)

        if self.left_child:
            self.left_child.preorder_recursive()
        if self.right_child:
            self.right_child.preorder_recursive()

    def preorder_iterative(self): # iterative
        stack = []
        stack.append(self)
        while stack: # while items on stack:
            node = stack.pop()
            print(node.key)
            if node.right_child: stack.append(node.right_child) # push right child
            if node.left_child: stack.append(node.left_child) # push left child

n1 = BinaryTree(1)
n2 = BinaryTree(2)
n3 = BinaryTree(3)
n4 = BinaryTree(4)
n5 = BinaryTree(5)
n6 = BinaryTree(6)
n7 = BinaryTree(7)

n1.left_child = n2
n1.right_child = n3
n2.left_child = n4
n2.right_child = n5
n3.left_child = n6
n3.right_child = n7

print("recursive:")
n1.preorder_recursive()
print("\niterative:")
n1.preorder_iterative()

Prints:

recursive:
1
2
4
5
3
6
7

iterative:
1
2
4
5
3
6
7

Python Demo

As a Node Iterator

class BinaryTree:
    def __init__(self, key):
        self.key = key
        self.left_child = None
        self.right_child = None

    def __str__(self):
        return "[{}; {}; {}]".format(self.key, self.left_child, self.right_child)

    def preorder_recursive(self): # recursively
        print(self.key)

        if self.left_child:
            self.left_child.preorder_recursive()
        if self.right_child:
            self.right_child.preorder_recursive()

    def preorder_iterative(self): # iterative
        stack = []
        stack.append(self)
        while stack: # while items on stack:
            node = stack.pop()
            yield node
            if node.right_child: stack.append(node.right_child) # push right child
            if node.left_child: stack.append(node.left_child) # push left child

    def __iter__(self):
        return self.preorder_iterative()


n1 = BinaryTree(1)
n2 = BinaryTree(2)
n3 = BinaryTree(3)
n4 = BinaryTree(4)
n5 = BinaryTree(5)
n6 = BinaryTree(6)
n7 = BinaryTree(7)

n1.left_child = n2
n1.right_child = n3
n2.left_child = n4
n2.right_child = n5
n3.left_child = n6
n3.right_child = n7

print("recursive:")
n1.preorder_recursive()
print("\niterative:")
for node in n1:
    print(node.key)

Prints:

1
2
4
5
3
6
7

iterative:
1
2
4
5
3
6
7

Upvotes: 1

Related Questions