Skip to main content

Iterative Postorder Traversal Using Single stack


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.

Code:


import java.util.ArrayList;
import java.util.Stack;

// A binary tree node
class Node 
{
 int data;
 Node left, right;

 Node(int item) 
 {
  data = item;
  left = right;
 }
}

class BinaryTree 
{
 Node root;
 ArrayList<Integer> list = new ArrayList<Integer>();

 // An iterative function to do postorder traversal 
 // of a given binary tree
 ArrayList<Integer> postOrderIterative(Node node) 
 {
  Stack<Node> s = new Stack<Node>();
  if(node==null){
      return list;}
      Node temp=node;
      System.out.println(s);
      do
  {
      
  while(temp!=null)
  {
      if(temp.right!=null)
      {
          s.push(temp.right);
      }
      s.push(temp);
      temp=temp.left;
  }
      temp=s.pop();
      if(temp.right!=null)
      {
          if(!s.empty() && temp.right==s.peek())
          {
              Node x=s.pop();
              s.push(temp);
              temp=x;
          }
          else{
              list.add(temp.data);
              temp=null;
          }
      }else{
              list.add(temp.data);
              temp=null;
              System.out.println("added to list"+list);
          }
  }while(!s.empty());
  
     return list;
 }
  

 // Driver program to test above functions
 public static void main(String args[]) 
 {
 BinaryTree tree = new BinaryTree();

  // Let us create trees shown in above diagram
  tree.root = new Node(1);
  tree.root.left = new Node(2);
  tree.root.right = new Node(3);
  tree.root.left.left = new Node(4);
  tree.root.left.right = new Node(5);
  tree.root.right.left = new Node(6);
  tree.root.right.right = new Node(7);

  ArrayList<Integer> mylist = tree.postOrderIterative(tree.root);
  
  System.out.println("Post order traversal of binary tree is :");
  System.out.println(mylist);
 }
}

Comments

Popular posts from this blog

A Very Basic yet important question in a life of a software developer

 Processes Vs Threads Process:  It is an execution unit where a program runs. The OS helps to create, schedule, and terminates the processes which is used by CPU. The other processes created by the main process are called child process. A process operations can be controlled with the help of PCB(Process Control Block). PCB contains all the crucial information related to processing like process id, priority, state, and contents CPU register, etc. Important properties of the process: - Creation of each process requires separate system calls for each process. - It is an isolated execution entity and does not share data and information. - Processes use the IPC(Inter-Process Communication) mechanism for communication that significantly increases the number of system calls. - Process management takes more system calls. - A process has its stack, heap memory, and data map. Thread:   A process can have multiple threads, all executing at the same time. A thread is lightw...

Count the Reversals

Problem Statement: Given a string  S  consisting only of opening and closing curly brackets  '{'  and  '}'  find out the minimum number of reversals required to make a balanced expression. Input The first line of input contains an integer  T  denoting the number of test cases. Then  T  test cases follow.  The first line of each test case contains a string  S  consisting only of  {  and  } . Output Print out minimum reversals required to make  S  balanced.If it cannot be balanced, then print  -1 . Constraints 1 <=  T  <= 100 0 <    S   <= 50 Examples   Input 4 }{{}}{{{ {{}}}} {{}{{{}{{}}{{ {{{{}}}} Output 3 1 -1 0 Expected Complexity Time :   O(n) Space : O(n) Code: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { Scanner sc=new Scanner(S...

CheatSheet for Searching Algorithms

CheatSheet for Searching Algorithms 1. Linear Search int search(int arr[], int x) { int n = arr.length; for(int i = 0; i < n; i++) { if(arr[i] == x) return i; } return -1; } The time complexity of above algorithm is O(n). 2. Binary Search // Returns location of key, or -1 if not found // Returns location of key, or -1 if not found int BinarySearch(int A[], int l, int r, int key) { int m; while( l <= r ) { m = l + (r-l)/2; if( A[m] == key ) // first comparison return m; if( A[m] < key ) // second comparison l = m + 1; else r = m - 1; } return -1; } The time complexity of Binary Search Theta(log(n)) Auxiliary Space: O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space. 3. The Ubiquitous Binary Search // Invariant: A[l] <= key and A[r] > key // Boundar...