Started by David HarrisonOct 2, 2021

# Opencan 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

Anik 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.`

You must be Logged in to reply
Trending Technologies
15
Software40
DevOps46
Frontend Development24
Backend Development20
Data Center24
Sentry24
Terraform23
Ansible83
Docker70
Penetration Testing16
Kubernetes21
NGINX20
JenkinsX17