Iterating over a Binary Tree with O(1) Auxiliary Space

Question

Is it possible to iterate over a binary tree in O(1) auxiliary space (w/o using a stack, queue, etc.), or has this been proven impossible? If it is possible, how can it be done?

Edit: The responses I've gotten about this being possible if there are pointers to parent nodes are interesting and I didn't know that this could be done, but depending in how you look at it, that can be O(n) auxiliary space. Furthermore, in my practical use case, there are no pointers to parent nodes. From now on, please assume this when answering.

Answer 1

Geez, I'll have to actually type it up from Knuth. This solution is by Joseph M. Morris [Inf. Proc. Letters 9 (1979), 197-200]. As far as I can tell, it runs in O(NlogN) time.

static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) {   Node parent = root ;   Node right  = null ;   Node curr ;   while (parent != null) {     curr = parent.left ;     if (curr != null) {       // search for thread       while (curr != right && curr.right != null)         curr = curr.right ;        if (curr != right) {         // insert thread         assert curr.right == null ;         curr.right = parent ;         preorderVisitor (parent) ;         parent = parent.left ;         continue ;       } else         // remove thread, left subtree of P already traversed         // this restores the node to original state         curr.right = null ;     } else       preorderVisitor (parent) ;      right  = parent ;     parent = parent.right ;   } }  class Node {   public Node left  ;   public Node right ; } 

Answer 2

It is possible if you have a link to the parent in every child. When you encounter a child, visit the left subtree. When coming back up check to see if you're the left child of your parent. If so, visit the right subtree. Otherwise, keep going up until you're the left child or until you hit the root of the tree.

In this example the size of the stack remains constant, so there's no additional memory consumed. Of course, as Mehrdad pointed out, links to the parents can be considered O(n) space, but this is more of a property of the tree than it is a property of the algorithm.

If you don't care about the order in which you traverse the tree, you could assign an integral mapping to the nodes where the root is 1, the children of the root are 2 and 3, the children of those are 4, 5, 6, 7, etc. Then you loop through each row of the tree by incrementing a counter and accessing that node by its numerical value. You can keep track of the highest possible child element and stop the loop when your counter passes it. Time-wise, this is an extremely inefficient algorithm, but I think it takes O(1) space.

(I borrowed the idea of numbering from heaps. If you have node N, you can find the children at 2N and 2N+1. You can work backwards from this number to find the parent of a child.)

Here's an example of this algorithm in action in C. Notice that there are no malloc's except for the creation of the tree, and that there are no recursive functions which means that the stack takes constant space:

#include <stdio.h> #include <stdlib.h>  typedef struct tree {   int value;   struct tree *left, *right; } tree;  tree *maketree(int value, tree *left, tree *right) {   tree *ret = malloc(sizeof(tree));   ret->value = value;   ret->left = left;   ret->right = right;   return ret; }  int nextstep(int current, int desired) {   while (desired > 2*current+1)       desired /= 2;    return desired % 2; }  tree *seek(tree *root, int desired) {   int currentid; currentid = 1;    while (currentid != desired)     {       if (nextstep(currentid, desired))     if (root->right)       {         currentid = 2*currentid+1;         root = root->right;       }     else       return NULL;       else     if (root->left)       {         currentid = 2*currentid;         root = root->left;       }     else       return NULL;     }   return root;   }   void traverse(tree *root) {   int counter;    counter = 1; /* main loop counter */    /* next = maximum id of next child; if we pass this, we're done */   int next; next = 1;     tree *current;    while (next >= counter)     {          current = seek(root, counter);       if (current)       {           if (current->left || current->right)               next = 2*counter+1;            /* printing to show we've been here */           printf("%i\n", current->value);       }       counter++;     } }  int main() {   tree *root1 =     maketree(1, maketree(2, maketree(3, NULL, NULL),                             maketree(4, NULL, NULL)),                 maketree(5, maketree(6, NULL, NULL),                             maketree(7, NULL, NULL)));    tree *root2 =       maketree(1, maketree(2, maketree(3,           maketree(4, NULL, NULL), NULL), NULL), NULL);    tree *root3 =       maketree(1, NULL, maketree(2, NULL, maketree(3, NULL,           maketree(4, NULL, NULL))));    printf("doing root1:\n");   traverse(root1);    printf("\ndoing root2:\n");   traverse(root2);    printf("\ndoing root3:\n");   traverse(root3); } 

I apologize for the quality of code - this is largely a proof of concept. Also, the runtime of this algorithm isn't ideal as it does a lot of work to compensate for not being able to maintain any state information. On the plus side, this does fit the bill of an O(1) space algorithm for accessing, in any order, the elements of the tree without requiring child to parent links or modifying the structure of the tree.