# Python Algorithm – Iterative Postorder Traversal | Set 2 (Using One Stack) Python Algorithm - Iterative Postorder Traversal | Set 2 (Using One Stack) - Stack - We have discussed a simple iterative postorder traversal

We have discussed a simple iterative postorder traversal using two stacks in the previous post. In this post, an approach with only one stack is discussed.

The idea is to move down to leftmost node using left pointer. While moving down, push root and root’s right child to stack. Once we reach leftmost node, print it if it doesn’t have a right child. If it has a right child, then change root so that the right child is processed before.

Following is detailed algorithm.

```1.1 Create an empty stack
2.1 Do following while root is not NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.```

Let us consider the following tree

Following are the steps to print postorder traversal of the above tree using one stack.

```1. Right child of 1 exists.
Push 3 to stack. Push 1 to stack. Move to left child.
Stack: 3, 1

2. Right child of 2 exists.
Push 5 to stack. Push 2 to stack. Move to left child.
Stack: 3, 1, 5, 2

3. Right child of 4 doesn't exist. '
Push 4 to stack. Move to left child.
Stack: 3, 1, 5, 2, 4

4. Current node is NULL.
Pop 4 from stack. Right child of 4 doesn't exist.
Print 4. Set current node to NULL.
Stack: 3, 1, 5, 2

5. Current node is NULL.
Pop 2 from stack. Since right child of 2 equals stack top element,
pop 5 from stack. Now push 2 to stack.
Move current node to right child of 2 i.e. 5
Stack: 3, 1, 2

6. Right child of 5 doesn't exist. Push 5 to stack. Move to left child.
Stack: 3, 1, 2, 5

7. Current node is NULL. Pop 5 from stack. Right child of 5 doesn't exist.
Print 5. Set current node to NULL.
Stack: 3, 1, 2

8. Current node is NULL. Pop 2 from stack.
Right child of 2 is not equal to stack top element.
Print 2. Set current node to NULL.
Stack: 3, 1

9. Current node is NULL. Pop 1 from stack.
Since right child of 1 equals stack top element, pop 3 from stack.
Now push 1 to stack. Move current node to right child of 1 i.e. 3
Stack: 1

10. Repeat the same as above steps and Print 6, 7 and 3.
Pop 1 and Print 1.```

Python Programming:

``````# Python program for iterative postorder traversal
# using one stack

ans = []

# A Binary tree node
class Node:

# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None

def peek(stack):
if len(stack) > 0:
return stack[-1]
return None
# A iterative function to do postorder traversal of
# a given binary tree
def postOrderIterative(root):

# Check for empty tree
if root is None:
return

stack = []

while(True):

while (root):
# Push root's right child and then root to stack
if root.right is not None:
stack.append(root.right)
stack.append(root)

# Set root as root's left child
root = root.left

# Pop an item from stack and set it as root
root = stack.pop()

# If the popped item has a right child and the
# right child is not processed yet, then make sure
# right child is processed before root
if (root.right is not None and
peek(stack) == root.right):
stack.pop() # Remove right child from stack
stack.append(root) # Push root back to stack
root = root.right # change root so that the
# righ childis processed next

# Else print root's data and set root as None
else:
ans.append(root.data)
root = None

if (len(stack) <= 0):
break

# Driver pogram to test above function
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)

print "Post Order traversal of binary tree is"
postOrderIterative(root)
print ans

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)``````

Output:

```Post Order traversal of binary tree is
[4, 5, 2, 6, 7, 3, 1]```
READ  C Program - Inorder Tree Traversal without Recursion #### Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

X