CareerCup

private static void inOrderTraversal(BinaryTreeNode root) {
		// TODO Auto-generated method stub
		Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
		while (true) {
			while (root != null) {
				s.push(root);
				root = root.getLeft();
			}
			if (s.isEmpty())
				return;

			root = (BinaryTreeNode) s.pop();
			System.out.println(root.getData());
			root = root.getRight();
		}

	}

time: O(N)
space: O(lgN) for balanced or O(N) for unbalanced tree

void inorderPrint(){
    	
    	Node<T> cur = root;
    	
    	Deque<Node<T>> stack = new ArrayDeque<>();
    	
    	while( cur != null ){
    		if( cur.left != null ){
    			stack.push(cur);
    			cur = cur.left;
    		}
    		else {
    			print( cur.value );
    			cur = cur.right;
    			while( cur == null && ! stack.isEmpty() ){
    				cur = stack.pop();
    				print( cur.value );
    				cur = cur.right;
    			}
    		}
    	}
    }

time complexity:O(n)
space complexity:O(1)

void MorrisTraversal(Node *root){
Node *p,prev;
p=root;
if(p==null) return;
while(p!=null){
if(p->left == null)
	{print p->data;p=p->right;continue;}
for(prev=p->left;prev->right != null && prev->right !=p;prev=prev->right){}
if(prev->right == null){
prev->right = p; p=p->left;continue;}
if(prev->right == p){
print p->Data;p=p->right;continue;}
}
}

public class InorderIteration {

private static Stack<Node> nodeStack= new Stack<Node>();
private static Set<Node> visited= new HashSet<Node>();

public static void main(String[] args){

Node head = createBST();

System.out.println("Inorder from recursion");
printInorder(head);

nodeStack.add(head);
System.out.println("\nInorder from iteration");
inorder();
}

private static void inorder() {

while(!nodeStack.empty()){

Node curr=nodeStack.pop();

if(visited.contains(curr)){ //to check if its backtracking

System.out.print(curr.getValue()+" ");

visited.remove(curr);
}else{

if(curr.getLeft()==null){
System.out.print(curr.getValue()+" ");
if(curr.getRight()!=null)
nodeStack.push(curr.getRight());
}
else{

if(curr.getRight()!=null)
nodeStack.push(curr.getRight()); //right first


nodeStack.push(curr); //parent
visited.add(curr); // to mark its visited

nodeStack.push(curr.getLeft());//left at last
}
}

}

}
public static Node addToBST(Node node, int value){

if(node==null){

node =new Node();
node.setValue(value);
return node;
}

if(node.getValue()>=value)
node.setLeft(addToBST(node.getLeft(),value));
else
node.setRight(addToBST(node.getRight(),value));




return node;
}

public static void printInorder(Node node){

if(node!=null){

printInorder(node.getLeft());
System.out.print(node.getValue()+" ");
printInorder(node.getRight());
}
}

public static Node createBST(){

Node head=addToBST(null,4);
head=addToBST(head,2);
head=addToBST(head,1);
head=addToBST(head,3);
head=addToBST(head,6);
head=addToBST(head,5);
head=addToBST(head,7);
head=addToBST(head,3);
head=addToBST(head,6);
head=addToBST(head,5);

return head;
}

public static class Node{

private Node left=null;
private Node right=null;
private int value;
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}


}

}

public class TreeNode<T> {
T value;
TreeNode left;
TreeNode right;

public TreeNode(TreeNode left, T value, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}

import java.util.Stack;

public class TreeIterativeTraversal {

public static <E> void inOrder(TreeNode<E> root) {

if(root == null) {
return;
}

Stack<TreeNode> nodeStack = new Stack<TreeNode>();

nodeStack.push(root);

TreeNode<E> currentNode, currentNodeClone;
while(!nodeStack.isEmpty()) {
currentNode = nodeStack.pop();

if(currentNode.left == null && currentNode.right == null) {
System.out.print(currentNode.value+" ");
continue;
}

if(currentNode.right != null) {
nodeStack.push(currentNode.right);
}

if(currentNode.left == null) {
System.out.print(currentNode.value+" ");
} else {
currentNodeClone = new TreeNode<E>(null, currentNode.value, null);
nodeStack.push(currentNodeClone);
nodeStack.push(currentNode.left);
}
}
}

public static void main(String []args) {
inOrder(root);
}
}

public class TreeNode<T> {
    T value;
    TreeNode left;
    TreeNode right;

    public TreeNode(TreeNode left, T value, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

import java.util.Stack;

public class TreeIterativeTraversal {

    private static TreeNode<Integer> root;

    static {

        TreeNode<Integer> one = new TreeNode<Integer>(null, 1, null);
        TreeNode<Integer> four = new TreeNode<Integer>(null, 4, null);
        TreeNode<Integer> eleven = new TreeNode<Integer>(null, 11, null);
        TreeNode<Integer> nine = new TreeNode<Integer>(null, 9, null);
        TreeNode<Integer> twenty= new TreeNode<Integer>(null, 20, null);

        TreeNode<Integer> three = new TreeNode<Integer>(one, 3, four);
        TreeNode<Integer> five = new TreeNode<Integer>(three, 5, nine);

        TreeNode<Integer> twelve = new TreeNode<Integer>(eleven, 12, null);
        TreeNode<Integer> fifthteen = new TreeNode<Integer>(twelve, 15, twenty);

        root = new TreeNode<Integer>(five, 10, fifthteen);
    }

    public static <E> void inOrder(TreeNode<E> root) {

        if(root == null) {
            return;
        }

        Stack<TreeNode> nodeStack = new Stack<TreeNode>();

        nodeStack.push(root);

        TreeNode<E> currentNode, currentNodeClone;
        while(!nodeStack.isEmpty()) {
            currentNode = nodeStack.pop();

            if(currentNode.left == null && currentNode.right == null) {
                System.out.print(currentNode.value+" ");
                continue;
            }

            if(currentNode.right != null) {
                nodeStack.push(currentNode.right);
            }

            if(currentNode.left == null) {
                System.out.print(currentNode.value+" ");
            } else {
                currentNodeClone = new TreeNode<E>(null, currentNode.value, null);
                nodeStack.push(currentNodeClone);
                nodeStack.push(currentNode.left);
            }
        }
    }

    public static void main(String []args) {
        inOrder(root);
    }
}

Use Collections.sort() that will arrange in increasing order. That will be inorder of tree.