Started by **David Harrison**Oct 2, 2021

Open

can we code inorder,preorder and postorder in single code in python ? without using recursionI 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

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

Trending Technologies

15

Software40

DevOps46

Frontend Development24

Backend Development20

Server Administration17

Linux Administration26

Data Center24

Sentry24

Terraform23

Ansible83

Docker70

Penetration Testing16

Kubernetes21

NGINX20

JenkinsX17

Recommended Threads

8

David Harrison