Unlike linear data structures (arrays, linked list, queues, stacks, etc.) which have only one logical way to traverse them but trees can be traversed in different ways. The following are commonly used methods for traversing trees.
Post-order Traversal of above tree (Left, Right, Root) : 4 5 2 3 1
Post-order Traversal Steps:
1. Traverse the left subtree, i.e., call Postorder(left-subtree) 2. Traverse the right subtree, i.e., call Postorder(right-subtree) 3. Visit the root.
Example – Program to traverse a tree in Post-Order without Recursion
import java.util.Stack;
public class PostOrderTraversal {
public static void main(String[] args) throws Exception {
Tree bt = new Tree();
Tree.TreeNode root = new Tree.TreeNode("1");
bt.root = root;
bt.root.left = new Tree.TreeNode("2");
bt.root.left.left = new Tree.TreeNode("4");
bt.root.left.right = new Tree.TreeNode("5");
bt.root.right = new Tree.TreeNode("3");
bt.postOrderWithoutRecursion();
}
}
class Tree {
static class TreeNode {
String data;
TreeNode left, right;
TreeNode(String value) {
this.data = value;
left = right = null;
}
boolean isLeaf() {
return left == null ? right == null : false;
}
}
TreeNode root;
public void postOrderWithoutRecursion() {
Stack<TreeNode> nodes = new Stack<TreeNode>();
nodes.push(root);
while (!nodes.isEmpty()) {
TreeNode current = nodes.peek();
if (current.isLeaf()) {
TreeNode node = nodes.pop();
System.out.printf("%s ", node.data);
} else {
if (current.right != null) {
nodes.push(current.right);
current.right = null;
}
if (current.left != null) {
nodes.push(current.left);
current.left = null;
}
}
}
}
}
Output
4 5 2 3 1
