Postorder Traversal Without Using Recursion With Two Stacks

Approach

We can do post order traversal iteratively using two stacks.

There are also approaches involving one stack, but this seems to be a simpler one to understand.

For a root element T1 with left child T2 and right child T3, post order traversal order will be T2, T3, and T1.

To make this happen, we should elements in the order T1, T2 and T3 into the second stack and then print them.

Approach can be summarized as:

  • Create two stacks s1 and s2.

  • Push root to first stack s1.

  • Loop while first stack s1 is not empty:

    • Pop a node from first stack s1 and push it to second stack s2

    • Push left and right children of the popped node to first stack s1

  • Print contents of second stack s2

 

Solution

void postorder(TreeNode n)

{

  TreeNode current = n;

  Stack s1 = new Stack();

  Stack s2 = new Stack();

  s1.push(current);

 

  while(!s1.isEmpty())

  {

    current = s1.pop();

    s2.push(current);

    s1.push(current.left);

    s1.push(current.right);

  }

 

  while(!s2.isEmpty())

  {

    current = s2.pop();

    print(current);

  }

}

 

Complexity

Time complexity will be in the order of N.

However, extra spaces will be taken for two stacks.

Quick Notes Finder Tags

Activities (1) advanced java (1) agile (3) App Servers (6) archived notes (2) Arrays (1) Best Practices (12) Best Practices (Design) (3) Best Practices (Java) (7) Best Practices (Java EE) (1) BigData (3) Chars & Encodings (6) coding problems (2) Collections (15) contests (3) Core Java (All) (55) course plan (2) Database (12) Design patterns (8) dev tools (3) downloads (2) eclipse (9) Essentials (1) examples (14) Exception (1) Exceptions (4) Exercise (1) exercises (6) Getting Started (18) Groovy (2) hadoop (4) hibernate (77) hibernate interview questions (6) History (1) Hot book (5) http monitoring (2) Inheritance (4) intellij (1) java 8 notes (4) Java 9 (1) Java Concepts (7) Java Core (9) java ee exercises (1) java ee interview questions (2) Java Elements (16) Java Environment (1) Java Features (4) java interview points (4) java interview questions (4) javajee initiatives (1) javajee thoughts (3) Java Performance (6) Java Programmer 1 (11) Java Programmer 2 (7) Javascript Frameworks (1) Java SE Professional (1) JPA 1 - Module (6) JPA 1 - Modules (1) JSP (1) Legacy Java (1) linked list (3) maven (1) Multithreading (16) NFR (1) No SQL (1) Object Oriented (9) OCPJP (4) OCPWCD (1) OOAD (3) Operators (4) Overloading (2) Overriding (2) Overviews (1) policies (1) programming (1) Quartz Scheduler (1) Quizzes (17) RabbitMQ (1) references (2) restful web service (3) Searching (1) security (10) Servlets (8) Servlets and JSP (31) Site Usage Guidelines (1) Sorting (1) source code management (1) spring (4) spring boot (3) Spring Examples (1) Spring Features (1) spring jpa (1) Stack (1) Streams & IO (3) Strings (11) SW Developer Tools (2) testing (1) troubleshooting (1) user interface (1) vxml (8) web services (1) Web Technologies (1) Web Technology Books (1) youtube (1)