Binary Search Tree Inorder Traversal

Question

I am confused by this code:

void in_order_traversal_iterative(BinaryTree *root) {
  stack<BinaryTree*> s;
  BinaryTree *current = root;
  while (!s.empty() || current) {
    if (current) {
      s.push(current);
      current = current->left;
    } else {
      current = s.top();
      s.pop();
      cout << current->data << " ";
      current = current->right;
    }
  }
}

We set a pointer to point to root. Then if it exists, then push the current (which is root currently) into the stack. I do not see why we push the whole tree into the stack initially, instead of just the value of the data the node holds. Am I missing something completely or not understanding why it would work this way? I cannot comprehend why we push the whole tree in, rather than a single node...

Answer 1

You're missing the fact that after a node is popped, its right child must still be traversed:

  current = s.top();
  s.pop();
  cout << current->data << " ";
  current = current->right;

If you had only the data on the stack, this would be impossible. The loop invariant is that the stack holds exactly those nodes with un-traversed right children.

Another way to see what's going on is to transform the recursive traversal to the iterative by algebra:

traverse(node) {
  if (node) {
    traverse(node->left);
    visit(node);
    traverse(node->right);
  }
}

First convert the tail call to iteration. We do this by updating the argument and replacing the recursive call with a goto the start of the function:

traverse(node) {
 start:
  if (node) {
    traverse(node->left);
    visit(node);
    node = node->right;
    goto start;
  }
}

The goto and if are the same as a while, so we have so far

traverse(node) {
  while (node) {
    traverse(node->left);
    visit(node);
    node = node->right;
  }
}

Replacing the other recursive call requires us to simulate the call stack of the compiler's runtime environment. We do that with an explicit stack.

traverse(node) {
 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
    goto start;         // simulate the recursive call
                        // recursive call was here; it's gone now!
   recursive_return:    // branch here to simulate return from recursive call
    visit(node);
    node = node->right;
  }
  // simulate the recursive return: if stack has args, restore and go to return site
  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    goto recursive_return;
  }
}

Though it's ugly, this is a way that always works to implement iterative versions of recursive code. (It's more complicated if there are multiple non-tail recursive calls, but not much.) And I'm sure you can see the similarity to your code.

We can even get rid of the ugliness with more algebra. First, it's not hard to see this code:

 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
    goto start;         // simulate the recursive call

when executed beginning with start is equivalent to

  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
  }

We can also replace

  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    goto recursive_return;
  }

with the following

  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    visit(node);
    node = node->right;
    goto start;
  }

We have merely copied the three instructions after recursive_return: into the if body.

With this, there is no way left to arrive at the recursive_return label, so we can delete it along with the two following statements:

   // Dead code!  Delete me!
   recursive_return:
    visit(node);
    node = node->right;

We now have:

traverse(node) {
 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
  }
  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    visit(node);
    node = node->right;
    goto start;
  }
}

We can get rid of the last goto start by replacing it with an endless loop:

traverse(node) {
  loop {
    while (node) {
      stack.push(node);        // save the value of the argument
      node = node->left;       // redefine it the same way the recursive call would have
    }
    if (stack.empty()) break;  // original code returns, so does this!
    node = stack.pop();        // restore the saved parameter value
    visit(node);
    node = node->right;
  }
}

Note we are returning under the same conditions as the previous code: the stack is empty!

I will let you prove to yourself that this code does the same as what you presented, only it's a bit more efficient because it avoids some comparisons! We never had to reason at all about pointers and stack elements. It "just happened."

Answer 2

It's not pushing the whole tree into the stack, it pushes the left-most part of the tree. Then it begin to pop the elements and push their right-most counterparts, in ascending order.