Tuesday, 4 August 2015

Post order Traversal- Binary Tree in java

Information about Tree : Tree Introduction
Pre-Order Traversal in Binary Tree

Post Order Traversal in Binary Tree: In Post order(Post fix), First we traversal through children(left to right manner) before traversing parent.

1. Traverse the left subtree by recursively calling the post-order function.
2. Traverse the right subtree by recursively calling the post-order function.
3. Display the data part of root element (or current element).

In the above Tree, before traversing 1, we have to traverse 2 and 3, and before traversing 2 we have to traversal 5 and 6. Same rule applies on all the node of tree. So Leftmost child would be traversed first and root node would be traversed at last.

Output: 9,5,6,2,8,410,7,3,1

Recursive Way:

public void postOrderRecusriveWay(BinaryDataTree<Integer> root) {
if (root == null) {
return;
}

postOrderRecusriveWay(root.getLeft());
postOrderRecusriveWay(root.getRight());
System.out.print(root.getData() + " ");
}

Iterative Way:

public void postOrderIterativeWay(BinaryDataTree<Integer> root) {

Stack<
BinaryDataTree<Integer>> s = new Stack<BinaryDataTree<Integer>>();
if (root == null)
return;

while (true) {
while (root != null) {
s.push(root);
root = root.getLeft();
}
if (s.isEmpty())
return;
root = s.peek().getRight();
if (root == null) {
root = s.pop();
System.out.print(root.getData() + " ");
while (!s.isEmpty() && root == s.peek().getRight()) {
root = s.pop();
System.out.print(root.getData() + " ");
}
root = null;

}
}
}