Binary Tree non-recursive traverse method.

package interview;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * None recursive pre-order, post-order and in-order.
 * In order to back trace, the main idea here is using a Node that point to the last
 * popped Node.
 * 
 * 
 * 
 * The last popped Node must have some kind of relationship with the current top Node in the stack.
 * 
 * 1. last Node is the child of top Node;
 * 2. last Node is the siblings of the top Node;
 * 3. last Node is the parent of the top Node;
 * 
 * 
 * A. For preOrder scenario, last Node is the parent of the top Node. We can also use the same thinking 
 * that we never pop-up the parent unless the 2 children are visited. But here we do not need that,
 * I found that the parent node is useless because when comes from right node, we certainly need to go back to the 
 * up level.
 * 

 * 
 * 
 * B. For inOrder and postOrder scenario, the last Node is the child or sibling of the top Node. We never pop-up the parent unless the 2 children are visited
 * 

 * @author wa505
 *
 */
public class BinaryTreeNoneRecursive {

	public static void main(String[] args) {
		
		Stack<Node> stack = new Stack<>();
		int i = 0;
		Node root = new Node();
		root.value = i++;
		stack.push(root);
		while (!stack.isEmpty() && i <= 6) {
			List<Node> tempList = new ArrayList<>();
			while (!stack.isEmpty()) {
				Node top = stack.pop();
				Node left = addLeft(top, i++);
				Node right = addRight(top, i++);
				tempList.add(right);
				tempList.add(left);
			}
			for (Node node : tempList) {
				stack.push(node);
			}
		}

		BinaryTreeNoneRecursive bTree = new BinaryTreeNoneRecursive();
		List<Node> preList = bTree.preOrder(root);
		System.out.println("================preList");
		for (Node node : preList) {
			System.out.println(node.value);
		}

		System.out.println("================inList");
		List<Node> inList = bTree.inOrder(root);
		for (Node node : inList) {
			System.out.println(node.value);
		}
		System.out.println("================postList");
		List<Node> postList = bTree.postOrder(root);
		for (Node node : postList) {
			System.out.println(node.value);
		}
	}

	static Node addLeft(Node node, int value) {
		Node child = new Node();
		child.value = value;
		node.left = child;
		return child;
	}

	static Node addRight(Node node, int value) {
		Node child = new Node();
		child.value = value;
		node.right = child;
		return child;
	}

	static class Node {
		int value;
		Node left;
		Node right;
	}

	List<Node> preOrder(Node root) {
		List<Node> result = new ArrayList<>();
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		while (stack.size() > 0) {
			Node node = stack.pop();
			if (node != null) {
				result.add(node);
				stack.push(node.right);
				stack.push(node.left);
			}
		}
		return result;
	}

	List<Node> inOrder(Node root) {
		List<Node> result = new ArrayList<>();
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		Node lastNode = null;
		while (stack.size() > 0) {
			Node top = stack.peek();
			if (top.right == lastNode && lastNode != null) {
				stack.pop();
				lastNode = top;
			} else if (top.left == lastNode && lastNode != null) {
				result.add(top);
				if (top.right == null) {
					stack.pop();
					lastNode = top;
				} else {
					stack.push(top.right);
				}
			} else if (top.left != null) {
				stack.push(top.left);
			} else if (top.right != null) {
				stack.push(top.right);
			} else {
				result.add(stack.pop());
				lastNode = top;
			}
		}
		return result;
	}

	List<Node> postOrder(Node root) {
		List<Node> result = new ArrayList<>();
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		Node lastNode = null;
		while (stack.size() > 0) {
			Node top = stack.peek();
			if (top.right == lastNode && lastNode != null) {
				stack.pop();
				lastNode = top;
				result.add(top);
			} else if (top.left == lastNode && lastNode != null) {
				if (top.right == null) {
					stack.pop();
					lastNode = top;
					result.add(top);
				} else {
					stack.push(top.right);
				}
			} else if (top.left != null) {
				stack.push(top.left);
			} else if (top.right != null) {
				stack.push(top.right);
			} else {
				stack.pop();
				lastNode = top;
				result.add(top);
			}
		}
		return result;
	}
}