Techiio-author
Started by David HarrisonOct 2, 2021

Open
can we code inorder,preorder and postorder in single code in python ? without using recursion

2 VIEWES 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 2 VIEWES SHARE

I want to code all binary tree orders in single code (preorder,postorder,inorder) in O(N) time complexity and O(N) space , using single stack and without recursion.

anybody can help me ?

1 Replies

Techiio-commentatorAnik Adhikary replied 8 days ago0 likes0 dislikes
# Python3 program for the above approach
# Structure of the
# node of a binary tree
class Node:
	def __init__(self, x):
		self.data = x
		self.left = None
		self.right = None
# Function to print all nodes of a
# binary tree in Preorder, Postorder
# and Inorder using only one stack
def allTraversal(root):
	# Stores preorder traversal
	pre = []
	# Stores inorder traversal
	post = []
	# Stores postorder traversal
	inn = []
	# Stores the nodes and the order
	# in which they are currently visited
	s = []
	# Push root node of the tree
	# into the stack
	s.append([root, 1])
	# Traverse the stack while
	# the stack is not empty
	while (len(s) > 0):
		# Stores the top
		# element of the stack
		p = s[-1]
		#del s[-1]
		# If the status of top node
		# of the stack is 1
		if (p[1] == 1):
			# Update the status
			# of top node
			s[-1][1] += 1
			# Insert the current node
			# into preorder, pre[]
			pre.append(p[0].data)
			# If left child is not NULL
			if (p[0].left):
				# Insert the left subtree
				# with status code 1
				s.append([p[0].left, 1])
		# If the status of top node
		# of the stack is 2
		elif (p[1] == 2):
			# Update the status
			# of top node
			s[-1][1] += 1
			# Insert the current node
			# in inorder, in[]
			inn.append(p[0].data);
			# If right child is not NULL
			if (p[0].right):
				# Insert the right subtree into
				# the stack with status code 1
				s.append([p[0].right, 1])
		# If the status of top node
		# of the stack is 3
		else:
			# Push the current node
			# in post[]
			post.append(p[0].data);
			# Pop the top node
			del s[-1]
	print("Preorder Traversal: ",end=" ")
	for i in pre:
		print(i,end=" ")
	print()
	# Printing Inorder
	print("Inorder Traversal: ",end=" ")
	for i in inn:
		print(i,end=" ")
	print()
	# Printing Postorder
	print("Postorder Traversal: ",end=" ")
	for i in post:
		print(i,end=" ")
	print()
# Driver Code
if __name__ == '__main__':
	# Creating the root
	root = Node(1)
	root.left = Node(2)
	root.right = Node(3)
	root.left.left = Node(4)
	root.left.right = Node(5)
	root.right.left = Node(6)
	root.right.right = Node(7)
	# Function call
	allTraversal(root)
	# This code is contributed by mohit kumar 29.

Hope this code will help you.

You must be Logged in to reply
Trending Technologies
15
Software40
DevOps46
Frontend Development24
Backend Development20
Server Administration17
Linux Administration26
Data Center24
Sentry24
Terraform23
Ansible83
Docker70
Penetration Testing16
Kubernetes21
NGINX20
JenkinsX17
Techiio-logo

Techiio is on the journey to build an ocean of technical knowledge, scouring the emerging stars in process and proffering them to the corporate world.

Follow us on:

Subscribe to get latest updates

You can unsubscribe anytime from getting updates from us
Developed and maintained by Wikiance
Developed and maintained by Wikiance