Iterative inorder traversal of a binary tree using constant space.

In order traversal of a binary tree can be performed using O(1) storage if the tree stores parent pointer. The trick is to look at possible directions we need to move in the tree.  As shown in the diagram below there are 3 directions that you can move in a binary tree. They are to the left, right or up. Given this all we need is to establish conditions that decides the movement. Consider last visited node as the node we were in before coming to the current node. Here are the cases:

1. If the last visited node is the parent node and the current node's left child exists move left.

2. If the last visited node is the left child of the current node and the current node has right child move right.

3. If the last visited node is on the left or right move up.

For the node to be the next successor for inorder traversal one of the following conditions should hold ( We will print the node value in our sample code below whenever this condition holds):

1. The last visited node was the left child.

2.  The left child of the current node doesn't exist.

It's now easy to translate these conditions into code. All you need is these conditions and some additional null checks as shown in the code below.

void inorder_constant_space(Node *root) {

    if (!root)
        return;

    Node *last = NULL;
    Node *node = root;

    while (node) {

        if (last == node->left || 
                (last == node->parent && node->left == NULL)) {
            std::cout << node->name;
        }

        if (last == node->left && node->right != NULL) {
            last = node;
            node = node->right;
        } else if(last == node->left) {
            last = node;
            node = node->parent;
        } else if (last == node->parent && node->left == NULL
                         && node->right != NULL) {
            last = node;
            node = node->right;
        } else if (last == node->parent && node->left == NULL) {
            last = node;
            node = node->parent;
        } else if (last == node->parent) {
            last = node;
            node = node->left;
        } else {
            last = node;
            node = node->parent;
        }
       
    }
}