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;
        }
       
    }
}

Iterative Inorder Traversal

Iterative inorder traversal is a little complicated than Preorder traversal. As for Preorder we need to use stack for Inorder traversal as well but the nodes can't be removed from stack until it's children are pushed to the stack and the node has been visited. For all nodes we need to push their children on the stack first before visiting it. We mark whether the children have been put into stack or not for a node my using another stack call marks. When adding children to the stack we set mark to true on the marks stack. Now when we pop the node again we check corresponding mark and if it is set to true we know that it's children has already been processed. Thus we visit the node (print the value in the code below). In Inorder traversal left child, parent and right child are processed respectively. So while pushing on the stack we do it on the reverse order so that Inorder requirements are maintained.

  
void inorder_traversal(Node *root) {
 if(root == 0)
  return;

 std::vector<bool> marks;
 std::vector<Node*>nodes;
 nodes.push_back(root);
 marks.push_back(false);

 while(!nodes.empty()){

//read the top mark
  bool mark = marks.back();
  marks.pop_back();

 //read the top node
  Node *node = nodes.back();
  nodes.pop_back();
 
 if(mark) {
 //if mark is set then the node is visited
   std::cout << node->value_ << std::endl;
  }
  else {
 //put the righ child on stack
   if(node->right_ != NULL) {
    nodes.push_back(node->right_);
    marks.push_back(false);
   }

 //set mark to true
 //put the node in the stack
   marks.push_back(true);
   nodes.push_back(node);

 //put left child on the stack
   if(node->left_ != NULL) {
    nodes.push_back(node->left_);
    marks.push_back(false);
   }
  }
 }
}
 

Iterative Preorder Traversal

Preorder traversal is easy when you consider recursive approach but it's quite tricky without recursion. The idea is to simulate recursion using stack. Start from the root and put the root's right and left child on the stack respectively. Then pop the topmost element from the stack, visit it and then again put it's right and left child on the stack if they exists. Continue this till the stack is empty.

  
void preorder_traversal(Node *root) {
 if(root == 0)
  return;

 std::vector stack;
 stack.push_back(root);
 Node *current;
 
 while ( !stack.empty()) {
  current = stack.back();
  stack.pop_back();
  
  std::cout << current->value_ << std::endl;
  
  if(current->right_ != NULL)
   stack.push_back(current->right_);
  if(current->left_ != NULL)
   stack.push_back(current->left_);
 }
}