Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time

I didn't think it through entirely, but i think it's possible as long as you're willing to mess up your tree in the process.

Every Node has 2 pointers, so it could be used to represent a doubly-linked list. Suppose you advance from Root to Root.Left=Current. Now Root.Left pointer is useless, so assign it to be Current.Right and proceed to Current.Left. By the time you reach leftmost child, you'll have a linked list with trees hanging off of some nodes. Now iterate over that, repeating the process for every tree you encounter as you go

EDIT: thought it through. Here's the algorithm that prints in-order:

void traverse (Node root) {
  traverse (root.left, root);
}

void traverse (Node current, Node parent) {
  while (current != null) {
    if (parent != null) {
      parent.left = current.right;
      current.right = parent;
    }

    if (current.left != null) {
      parent = current;
      current = current.left;
    } else {
      print(current);
      current = current.right;
      parent = null;
    }
  }
}

How about Morris Inorder tree traversal? Its based on the notion of threaded trees and it modifies the tree, but reverts it back when its done.

Linkie: http://geeksforgeeks.org/?p=6358

Doesn't use any extra space.

If you are using a downwards pointer based tree and don't have a parent pointer or some other memory it is impossible to traverse in constant space.

It is possible if your binary tree is in an array instead of a pointer-based object structure. But then you can access any node directly. Which is a kind of cheating ;-)

Here's a shorter version iluxa's original answer. It runs exactly the same node manipulation and printing steps, in exactly the same order — but in a simplified manner [1]:

void traverse (Node n) {
  while (n) {
    Node next = n.left;
    if (next) {
      n.left = next.right;
      next.right = n;
      n = next;
    } else {
      print(n);
      n = n.right;
    }
  }
}

[1] Plus, it even works when the tree root node has no left child.