Traversing a tree using Postorder traveral iteratively

package in.blogspot.arunj2ee.ds.tree.traversal;

import in.blogspot.arunj2ee.ds.tree.BinaryTreeNode;
import in.blogspot.arunj2ee.ds.tree.util.TreeUtil;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Traversing a tree using Postorder traveral iteratively
 * Preorder ==> Left,Right,Node
 * Time Complexity: O(n), Space Complexity: O(n)
 * @author Arun.Singh
 *
 */
public class PostOrderTraversalIterative {

public static ArrayList<Integer> postOrderTraversal(BinaryTreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null)
return res;

Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
s.push(root);

BinaryTreeNode prev = null;

while (!s.isEmpty()) {
BinaryTreeNode curr = s.peek();
if (prev == null || prev.getLeft() == curr || prev.getRight() == curr) {
// traverse from top to buttom, and if curr has left child or
// right child,
// push into stack; otherwise, pop out.
if (curr.getLeft() != null)
s.push(curr.getLeft());
else if (curr.getRight() != null)
s.push(curr.getRight());
} else if (curr.getLeft() == prev) {
if (curr.getRight() != null)
s.push(curr.getRight());
} else {
res.add(curr.getData());
s.pop();
}
prev = curr;
}
return res;
}

// [4, 5, 2, 6, 7, 3, 1]
public static void main(String[] args) {
System.out.println(postOrderTraversal(TreeUtil.makeSampleBinaryTree()));
}
}

========================================================================

Refer Core Classes: http://arunj2ee.blogspot.in/2017/05/tree-core-and-utility-classes.html

========================================================================

Share on Google Plus

About Admin

Arun is a JAVA/J2EE developer and passionate about coding and managing technical team.