fork download
copy 
  1. /* package whatever; // don't place package name! */
  2. import java.util.Stack;
  3.  
  4. /**
  5.  * Iterative Post-order traversal using Single Stack 
  6.  * @author PRATEEK
  7.  */
  8.  class IterativePostOrderSingleStack {
  9.  
  10. 	/**
  11. 	 * Iterative Pre-order traversal using single stacks
  12. 	 */
  13. 	public void iterativePostOrder(Node root) {
  14. 		Stack<Node> stack = new Stack<Node>();
  15. 		Node curr = root;
  16. 		for (;;) 
  17. 		{
  18. 			if (curr != null) 
  19. 			{
  20. 				if (curr.right != null)
  21. 					stack.push(curr.right);
  22.  
  23. 				stack.push(curr);
  24. 				curr = curr.left;
  25. 			} 
  26. 			else 
  27. 			{
  28. 				if (!stack.isEmpty())
  29. 				{
  30. 					curr = stack.pop();
  31. 					// odd case, exchange curr and top element
  32. 					if (!stack.isEmpty() && curr.right == stack.peek()) 
  33. 					{
  34. 						stack.pop();
  35. 						stack.push(curr);
  36. 						curr = curr.right;
  37. 					}
  38. 					else
  39. 					{
  40. 						System.out.print(curr+"\t");
  41. 						curr=null; //move to right or null
  42. 					}
  43.  
  44. 				} else
  45. 					break;
  46. 			}
  47. 		}
  48. 	}
  49.  
  50. 	public static void main(String[] args) {
  51. 		Node root = new Node(12);
  52. 		root.left = new Node(8);
  53. 		root.left.left = new Node(6);
  54. 		root.left.right = new Node(10);
  55.  
  56. 		root.right = new Node(16);
  57. 		root.right.left = new Node(14);
  58. 		root.right.right = new Node(20);
  59.  
  60. 		IterativePostOrderSingleStack obj = new IterativePostOrderSingleStack();
  61. 		obj.iterativePostOrder(root);
  62. 	}
  63. }
  64. class Node implements Comparable<Node> {
  65. 	public Node left;
  66. 	public int data;
  67. 	public Node right;
  68.  
  69. 	public Node(int val)
  70. 	{
  71. 		this.data=val;
  72. 	}
  73.  
  74. 	@Override
  75. 	public int compareTo(Node that) {
  76. 		return this.data - that.data ;
  77. 	}
  78.  
  79. 	@Override
  80. 	public String toString(){
  81. 		return this.data + "";
  82. 	}
  83. }
  84.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6	10	8	14	20	16	12
https://ideone.com/I7gVsG
Iterative Post Order using Single Stack
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!