Tree Traversal without recursion and without stack and without changing the Tree

Here's a solution:

• Let current store the currently visited node (initialized to the root of the tree)
• Let origin represent how we got to the current node. It's one of FROM_PARENT, FROM_LEFT_CHILD, FROM_RIGHT_CHILD. (Initialized to FROM_PARENT)

Algorithm:

• If we came from the top, we print the key and go down left
• If we came back from left, go down right
• If we came back form right, go up.

origin = FROM_PARENT;
current = root;

while (current != null) {

    switch (origin) {

    case FROM_PARENT:
        System.out.println(current.key);
        if (current.left != null)
            goLeft();
        else
            origin = FROM_LEFT_CHILD;
        break;

    case FROM_LEFT_CHILD:
        if (current.right != null)
            goRight();
        else
            origin = FROM_RIGHT_CHILD;
        break;

    case FROM_RIGHT_CHILD:
        goToParent();
        break;
    }            
}

Where

static void goToParent() {
    if (current.parent == null) {
        current = null;
        return;
    }
    origin = current == current.parent.left ? FROM_LEFT_CHILD
                                            : FROM_RIGHT_CHILD;
    current = current.parent;
}

static void goLeft() {
    origin = FROM_PARENT;
    current = current.left;
}

static void goRight() {
    origin = FROM_PARENT;
    current = current.right;
}