pythonpython-3.xbinary-treetree-traversalinorder

Why is inorder tree traversal without recursion in Python running infinitely?


I'm trying to do Inorder tree traversal for binary trees without using recursion but it seems like the while loop keeps running infinitely. Any help would be appreciated.

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


def inOrder(root):
    s = []
    while s is not None or root is not None:
        if root is not None:
            s.append(root.left)
            if root.left:
                root = root.left
        else:
            root = s.pop()
            print(root.data)
            if root.right:
                root = root.right


if __name__=='__main__':

    root = Node(5)
    root.left = Node(3)
    root.left.right = Node(2)
    root.left.left = Node(4)
    root.right = Node(10)
    root.right.left = Node(9)
    root.right.right = Node(20)

#            5 
#          /   \ 
#         3     10 
#       /  \   /  \
#      4    2 9    20

    inOrder(root)

Solution

  • Check the following code for inorder traversal:

    class Node:
        def __init__(self, data):
            self.left = None
            self.right = None
            self.data = data
    
    
    def inOrder(root):
        s = []
        s.append(root)
        while len(s) > 0: # Check if stack is not empty
            if root.left: #Case 1: Traverse left if there is an element left of the current root
                s.append(root.left)
                root = root.left
            else:
                root = s.pop() #Case 2: If there is no element on the left, print the current root
                print(root.data)
                if root.right: #Case 3: If there is an element on the right, traverse right of the current root
                    s.append(root.right)
                    root = root.right
    
    
    if __name__=='__main__':
    
        root = Node(5)
        root.left = Node(3)
        root.left.right = Node(2)
        root.left.left = Node(4)
        root.right = Node(10)
        root.right.left = Node(9)
        root.right.right = Node(20)
        inOrder(root)