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
Post a Comment