CareerCup

1) One way is to use an additional stack.

2) Another way that uses no stack also is: Morris Algorithm
http : // stackoverflow.com / questions / 5502916 / please-explain-morris-inorder-tree-traversal-without-using-stacks-or-recursion

- -- March 13, 2012 | Flag Reply

{{{ here the algo: int top=-1; void inorder(struct btnode *rt) { do { if(rt!=NULL) { stack[++top]=rt; rt=rt->lc; } else { rt=stack[top--]; printf("%c",rt->info); rt=rt->rc; } }while(top || rt!=NULL); } - Anonymous March 14, 2012 | Flag Reply

void inorder(struct node *node){
Stack s;
do{
while(node != null){
push(s,node);
node = node->left;
}
if(!isempty(s)){
struct node * temp = pop(s);
printf("%d",temp->data);
node = temp->right;
}
} while(!isempty(s) || (node!=null));
}

- rkt March 15, 2012 | Flag Reply

here is the basic outline {{{ stack.push(root) while( root->left ) { stack.push(root->left); root = root->left; } // reached a point where there is no more left subtree so you got to print here unconditonally temp = stack.pop(); while(temp ! = null) { print(temp); if( temp ->right != null) // if right sub tree is non null you start with right child as new root node ! { root = temp->right; stack.push(root); break; // and proceed from again from the main while loop ! } else { if( stack.empty() ) temp = null; else temp = stack.pop(); // keep popping and printing as long as the right child is null } - Anonymous March 16, 2012 | Flag Reply

public static void inorder(Node root){
		Node node=root;
		Stack<Node> s=new Stack<Node>();
		while(!s.isEmpty()||node!=null){
			if(node!=null){
				s.push(node);
				node=node.left;
			}else{
				System.out.print(s.peek().data+" ");
				node=s.pop().right;
			}
		}
		System.out.println();
	}

- anonymous April 08, 2012 | Flag Reply

Another solution, albeit lengthier:

public static void myinorder(Node root) {
        Node node = root;
        Stack<Node> stack = new Stack<Node>();
        stack.push(node);

        while (!stack.isEmpty()) {
            while ((node != null) && (node.left != null)) {
                stack.push(node.left);
                node = node.left;
            }

            System.out.print(stack.peek().value + " ");

            if ((stack.peek().right == null) && (node != null) &&
                    (stack.peek() == node)) {
                stack.pop();
                node = null;
            } else if ((stack.peek().right != null) && (node != null) &&
                    (stack.peek() != node)) {
                node = stack.pop();
                node = stack.peek();
            }
            else if ((stack.peek().right != null) && (node != null)) {
                node = stack.pop().right;
                stack.push(node);
            }
            else if ((stack.peek().right != null) && (node == null)) {
                stack.push(stack.pop().right);
                node = stack.peek();
            }
        }
    }

- Yev August 12, 2012 | Flag Reply

Alternate solution:
public static void myinorder2(Node root) {
        Node node = root;
        Stack<Node> stack = new Stack<Node>();
    
      

        while (!stack.isEmpty() || node!=null) {
            //System.out.println("Stack: " + stack);

            if (node!=null) {
                stack.push(node);
                node = node.left;
            }
            else {
            	
                //System.out.println("\nStack: " + stack);
              
                if(node!=null)
                {
                	System.out.print(node.value+" ");
                }
                
                Node tmp = stack.pop();
                //System.out.println("\nStack: " + stack);
                if(tmp !=null && tmp != node)
                {
                	System.out.print(tmp.value+" ");
                }
                
       
                //System.out.println("\nStack: " + stack);
                if(tmp != null && tmp==node)
                {
                	tmp=stack.pop();
                	System.out.print(tmp.value+" ");
                }
                
                node = tmp.right;
                
                //System.out.println("\nNew right: " + node);
                //System.out.println("Stack: " + stack);
            }
          
        }
    }

- Yev August 12, 2012 | Flag Reply

Another solution, somewhat more intuitive:

public static void myinorder(Node root) {
        Node node = root;
        final Stack<Node> stack = new Stack<Node>();

        stack.push(root);

        while (!stack.isEmpty()) {
            if (node == null) {
                System.out.print(stack.peek().value + " ");
                node = stack.pop().right;

                if (node != null) {
                    stack.push(node);
                }
            } else if (node.left != null) {
                stack.push(node.left);
                node = node.left;
            } else if (node.left == null) {
                System.out.print(stack.peek().value + " ");

                node = stack.pop().right;
            }
        }
    }

- Yev August 13, 2012 | Flag Reply

Node root = new Node(5);
Node node = root;
BinarySearchTree bst = new BinarySearchTree();
bst.createBst(bst, root);
final Stack<Node> stack = new Stack<Node>();
stack.push(root);
Node trav;
trav = root;
while (!stack.isEmpty()) {
while(trav.left != null){
stack.push(trav.left);
trav = trav.left;
}
if(!stack.isEmpty()){
Node lastNode = stack.pop();
System.out.println(lastNode.value+" ");
if(lastNode.right != null){
stack.push(lastNode.right);
trav=lastNode.right;
}
}
}

- Manish Sharma August 27, 2013 | Flag Reply