EDUCBA Logo

EDUCBA

MENUMENU
  • Explore
    • EDUCBA Pro
    • PRO Bundles
    • Featured Skills
    • New & Trending
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign Up
Home Data Science Data Science Tutorials Data Structures Tutorial PostOrder Traversal without Recursion
 

PostOrder Traversal without Recursion

Updated March 14, 2023

PostOrder Traversal without Recursion

 

 

Introduction to PostOrder Traversal without Recursion

PostOrder Traversal without Recursion is a traversal method, where the left subtree is visited first, then right sub tree, and finally root node. Unlike array and linked lists, being linear data structures, we have several ways of traversing binary tree due to its hierarchical nature. It is also known as Iterative PostOrder Traversal, which is used to delete nodes in a Binary tree.

Watch our Demo Courses and Videos

Valuation, Hadoop, Excel, Mobile Apps, Web Development & many more.

PostOrder Traversal without Recursion is more complex than InOrder and PreOrder Traversals, but PostOrder can be easily done using two stacks. Traversing Binary tree involves iterating over all the nodes of Binary Tree in a manner. As trees are not a part of linear data structure, there can be a possibility of more than 1 possible next node from a given node.

Syntax:

PostOrder Traversal does not have a particular syntax, but it is just the way users code, i.e., Algorithm or the Flowchart.

Algorithm of PostOrder Traversal without Recursion

To create an empty stack.

Follow the below steps while the root node is not NULL.

  • Push the root node’s right child node to stack and then the root node.
  • Set root node as root node’s left child node.

Pop one item from the stack and set it as the root node.

  • If the item popped from the stack has a right child node and a right child node at the top, then the right child node is removed from the stack. Push the root node back and set the root node as the root node’s right child node.
  • Else print the root node’s value and set the root node to NULL.

Repeat these steps until the stack is empty.

Let us consider an example and use PostOrder Traversal without Recursion using 1 Stack.

Postorder Traversal without Recursion 1

How PostOrder Traversal is Done?

For the above example, we shall do a manual Postorder Traversal without Recursion.

Step 1: As the right child of A exists, C will be pushed to the stack and then A.

Stack: C, A
Move to the left child now.

Step 2: As the right child of B exists, E will be pushed to the stack and then B.

Stack: C, A, E, B
Move to the left child now.

Step 3: As the right child of D does not exist, D will be pushed to the stack.

Stack: C, A, E, B, D
Move to left child.

Step 4: As the current node is NULL, pop out D from the stack and, as the right child of D, does not exist. Set the current node to value NULL.

Stack: C, A, E, B

Step 5: As the current node is NULL, pop out B from the stack, and as the right child B equals the top element in the stack, pop out E from the stack and push B to the stack.

Stack: C, A, B

Step 6: As the right child of E does not exist, move E to stack and move to the left child.

Stack: C, A, B, E

Step 7: As the current node is NULL, pop out E from the stack and as the right child of E does not exist, print E and set the current node to NULL.

Stack: C, A, B

Step 8: As the current node is NULL, pop out B from the stack. As the right child of B is not equal to the top element in the stack. Print out B and set the current node to value NULL.

Stack: C, A

Step 9: As the current node is NULL, pop out A from the stack. As the right child of A equals the top element stack, pop out C from the stack, push A to the stack, and move the current node to the right child of A, i.e., C.

Stack: A

Step 10: Repeat the above steps and print out F, G, and C. Pop out A and print it out.

Example of PostOrder Traversal without Recursion

Given below is the example of PostOrder Traversal without Recursion:

Now, let us implement it using any programming language.

PostOrder Traversal without Recursion using Java.

Code:

import java.util.Stack;
class PostOrderNode
{
int val;
PostOrderNode leftNode, rightNode;
public PostOrderNode(int keyVal)
{
val = keyVal;
leftNode = rightNode = null;
}
}
class Main
{
public static void iterativePostOrder (PostOrderNode rootNode)
{
Stack<PostOrderNode> stack = new Stack();
stack.push(rootNode);
Stack<Integer> out = new Stack();
while (!stack.empty())
{
PostOrderNode currentNode = stack.pop();
out.push(currentNode.val);
if (currentNode.leftNode != null) {
stack.push(currentNode.leftNode);
}
if (currentNode.rightNode != null) {
stack.push(currentNode.rightNode);
}
}
while (!out.empty()) {
System.out.print(out.pop() + " ");
}
}
public static void main(String[] args)
{
PostOrderNode rootNode = new PostOrderNode(25);
rootNode.leftNode = new PostOrderNode(35);
rootNode.rightNode = new PostOrderNode(45);
rootNode.leftNode.leftNode = new PostOrderNode(55);
rootNode.leftNode.rightNode = new PostOrderNode(65);
rootNode.rightNode.leftNode = new PostOrderNode(75);
rootNode.rightNode.rightNode = new PostOrderNode(85);
iterativePostOrder(rootNode);
}
}

Output:

Postorder Traversal without Recursion 2

Here, as per the program, only one stack is being used, and postorder traversal is done without any recursion, i.e., iterative mode.

Conclusion

With this example, we have got to know How PostOrder traversal is done without recursion, i.e., in an iterative manner. We can now conclude the topic “PostOrder Traversal without Recursion”. We have seen what PostOrder traversal is and how is it implemented with a live example, solved manually. We have also seen Java programs written for PostOrder Traversal without any recursion, in an iterative manner using Stack.

Recommended Articles

This is a guide to PostOrder Traversal without Recursion. Here we discuss the introduction, algorithm and example, respectively. You may also have a look at the following articles to learn more –

  1. Stack in Data Structure
  2. Tree Traversal in Data Structure
  3. Heap Data Structure
  4. Hashing in Data Structure

Primary Sidebar

Footer

Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2025 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA Login

Forgot Password?

🚀 Limited Time Offer! - 🎁 ENROLL NOW