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