Coding Interview Club

Prepare for coding interviews in simple and structured steps

Postorder Traversal Without Using Recursion With One Stack

Category: 
Problem: 

Postorder Traversal Without Using Recursion With One Stack

Solution: 

In this solution we will be using only one stack.

void postorder(TreeNode n)

{

  if (n == null) return;

 

  TreeNode current = n;

  Stack s = new Stack();

  do{

  while(current!=null)

  {

    if(current.right!=null) s.push(current.right);

    s.push(current);

    current = current.left;

  }

  if(current.right ! = null && current.right == stack.peep())

  { //swap them

    stack.pop();

    stack.push(current);

    current = current.right;

  }

  else{

    print(current);

    current = null;

  }

  } while(!s.isEmpty());

}

 

Complexity

Complexity will be in the order on N.

Extra space will be taken for one stack. 

Back to Top