Inorder traversal of binary tree using stack in python

Python program for Inorder traversal of binary tree using stack. Here problem description and explanation.

#  Python 3 program for
#  Inorder traversal without recursion
#  Using stack

#  Binary Tree node
class TreeNode :
	#  Make a tree node
	def __init__(self, data) :
		#  Set node data
		self.data = data
		self.left = None
		self.right = None
	

class StackNode :
	def __init__(self, element) :
		self.element = element
		self.next = None
	

#  Stack Class
class MyStack :
	def __init__(self) :
		self.top = None
		self.size = 0
	
	#  Add new element into stack
	def push(self, element) :
		#  Create new node
		node = StackNode(element)
		node.next = self.top
		#  new node is new top
		self.top = node
		#  Increase the size
		self.size += 1
	
	#  Remove top element of the stack
	def pop(self) :
		if (self.top != None) :
			#  next node is new top
			self.top = self.top.next
			#  Reduce size
			self.size -= 1
		
	
	#  Returns the status of empty or non empty stacks
	def isEmpty(self) :
		if (self.size > 0 and self.top != None) :
			return False
		else :
			return True
		
	
	#  Return top element of stack
	def peek(self) :
		if (self.isEmpty()) :
			return None
		
		return self.top.element
	

class BinaryTree :
	def __init__(self) :
		self.root = None
	
	#  Display Inorder view of binary tree
	def inorder(self) :
		if (self.root != None) :
			#  Make new stack
			s = MyStack()
			node = self.root
			#  Display tree element
			while (not s.isEmpty() or node != None) :
				if (node != None) :
					#  Add current node
					s.push(node)
					#  Visit to left subtree
					node = node.left
				else :
					#  When node is null
					#  Get stack top element
					node = s.peek()
					#  Display node value
					print(" ", node.data, end = "")
					#  Remove top element of the stack
					s.pop()
					#  Visit to left subtree of current node
					node = node.right
				
			
		else :
			print("Empty Linked List")
		
	

def main() :
	#  Create new tree
	tree = BinaryTree()
	#    Construct Binary Tree
	#    -----------------------
	#        15
	#       /  \
	#      24   54
	#     /    /  \
	#    35   62   13
	#  Add tree nodes
	tree.root = TreeNode(15)
	tree.root.left = TreeNode(24)
	tree.root.right = TreeNode(54)
	tree.root.right.right = TreeNode(13)
	tree.root.right.left = TreeNode(62)
	tree.root.left.left = TreeNode(35)
	#  Display result
	tree.inorder()

if __name__ == "__main__": main()

Output

  35  24  15  62  54  13


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved