Engineering Full Stack Apps with Java and JavaScript
In this solution we will be using only one stack.
Solution
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 will be in the order on N.
Extra space will be taken for one stack.