CODEWITHSUNDEEP
pythoniterationbinary-treeinorderpreorder
DannyJ108
DannyJ108

Reputation: 11

Iterative inOrder Binary Tree

I have the following class for the creation of a Binary Tree:

class BinaryTree:

    def __init__(self):
        self._root = None
        self._left = None
        self._right = None

    def root(self):
        return self._root

    def left(self):
        return self._left

    def right(self):
        return self._right

    def isEmpty(self):
        return self._root is None

    def insert(self, element):
        if self.isEmpty():
            self._root = element
            self._left = BinaryTree()
            self._right = BinaryTree()
        elif element <= self._root:
            self._left.insert(element)
        elif element > self._root:
            self._right.insert(element)

    def inOrder(self):
        if self.isEmpty():
            return []
        l = self._left.inOrder()
        l.append(self._root)
        l += self._right.inOrder()
        return l

    def preOrder(self):
        if self.isEmpty():
            return []
        l = [self._root]
        l += self._left.preOrder()
        l += self._right.preOrder()
        return l

    def inOrder_iterative(self):
        stack = []
        res = []
        aux = self

        while aux or stack:
           
            while aux:
                stack.append(aux)
                aux = aux._left

            aux = stack.pop()
            res.append(aux._root)
            aux = aux._right

        return res

When I insert the binary tree for inorder(2, 3, 4, 5, 6, 7, 8), I get it in order but with "None" preceding each number as follows:

[None, 2, None, 3, None, 4, None, 5, None, 6, None, 7, None, 8, None]

I need it to output:

[2, 3, 4, 5, 6, 7, 8]

I can't seem to find what the error in the code is. Could you help me out please?

Thanks

EDIT:

Code to insert data into tree:

tree=BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(4)
tree.insert(2)
tree.insert(7)
tree.insert(6)
tree.insert(8)
print('The binary tree is: ')
print('inOrder recursive', tree.inOrder())
print('inOrden iterative', tree.inOrder_iterative())

Upvotes: 1

Views: 80

Answers (3)

trincot
trincot

Reputation: 351288

The problem is that you have not used the isEmpty method (which you do use in the recursive version). Change both occurrences of aux in your while conditions to not aux.isEmpty() and it will work.

As you have made a design decision to represent NIL as empty nodes (with _root equal to None), you should not check for BinaryTree instances to be None, but use the isEmpty logic.

    def inOrder_iterative(self):
        stack = []
        res = []
        aux = self
    
        while not aux.isEmpty() or stack:
    
            while not aux.isEmpty():
                stack.append(aux)
                aux = aux._left
    
            aux = stack.pop()
            res.append(aux._root)
            aux = aux._right
    
        return res

Upvotes: 0

Woodford
Woodford

Reputation: 4449

    def inOrder_iterative(self):
        stack = []
        res = []
        aux = self

        while aux or stack:
           
            while aux:
                stack.append(aux)
                aux = aux._left

            aux = stack.pop()
            res.append(aux._root)  # <-- aux may be empty here
            aux = aux._right

        return res

When you pop the next node off the stack you need to check to see if it's a leaf node before appending its value to the result. Change the indicated line to:

if not aux.isEmpty():
    res.append(aux._root)

Upvotes: 0

Nishant Kumar
Nishant Kumar

Reputation: 1

def iterative_inorder(root):
  stack = []
  current = root
  while current or stack:
    while current:
      stack.append(current)
      current = current.left
    if stack:
      current = stack.pop()
      print(current.data)
      current = current.right

Upvotes: 0

Related Questions