Skip to content

Instantly share code, notes, and snippets.

@rishabh1403
Created July 30, 2016 09:13
Show Gist options
  • Save rishabh1403/0ac66b681ed66a3918f0b002a0468f52 to your computer and use it in GitHub Desktop.
Save rishabh1403/0ac66b681ed66a3918f0b002a0468f52 to your computer and use it in GitHub Desktop.
Recursive and iterative PostOrder tree traversal
//TODO add iterative with single stack
import java.util.*;
//Node class
class Node{
int data;
Node left;
Node right;
Node(int data){
this.data = data;
this.left=null;
this.right = null;
}
}
public class PostOrder {
public static void main(String args[]){
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
//root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
iterativePostOrder(root);
System.out.println();
recursivePostOrder(root);
}
//recursive method
private static void recursivePostOrder(Node root) {
// TODO Auto-generated method stub
if(root != null){
recursivePostOrder(root.left);
recursivePostOrder(root.right);
System.out.print(root.data+" ");
}
//System.out.println();
}
//iterative method
private static void iterativePostOrder(Node root) {
// TODO Auto-generated method stub
if(root == null)
return;
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(root);
while(!s1.isEmpty()){
Node t = s1.pop();
if(t.left!=null)s1.push(t.left);
if(t.right!=null)s1.push(t.right);
s2.push(t);
}
while(!s2.isEmpty()){
System.out.print(s2.pop().data);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment