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

To preserve the tree and only use O(1) space it's possible if...

• Each node is a fixed size.
• The whole tree is in a contiguous part of memory (i.e. an array)
• You don't iterate over the tree, you simply iterate over the array

Or if you destroy the tree as you process it...:

• @Svante came up with this idea, but I wanted to expand on how a little, using a destructive approach.
• How? You can continue to take the left most leaf node in a tree (for(;;) node = node->left etc... , then process it, then delete it. If the leftmost node in the tree is not a leaf node, then you process and delete the right node's left most leaf node. If a right node has no children, then you process and delete it.

Ways that it wouldn't work...

If you use recursion you will use a stack implicitly. For some algorithms (not for this problem) tail recursion would allow you to use recursion and have O(1) space, but since any particular node may have several children, and hence there is work to do after the recursive call, O(1) space tail recursion is not possible.

You could try to tackle the problem 1 level at a time, but there is no way to access an arbitrary level's nodes without auxiliary (implicit or explicit) space. For example you could recurse to find the node you want, but then that takes implicit stack space. Or you could store all your nodes in another data structure per level, but that takes extra space too.

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.

Answer 3

You can achieve this if nodes have pointers to their parents. When you walk back up the tree (using the parent pointers) you also pass the node you're coming from. If the node you're coming from is the left child of the node you're now at, then you traverse the right child. Otherwise you walk back up to it's parent.

EDIT in response to the edit in the question: If you want to iterate through the whole tree, then no this is not possible. In order to climb back up the tree you need to know where to go. However, if you just want to iterate through a single path down the tree then this can be achieved in O(1) additional space. Just iterate down the tree using a while loop, keeping a single pointer to the current node. Continue down the tree until you either find the node you want or hit a leaf node.

EDIT: Here's code for the first algorithm (check the iterate_constant_space() function and compare to the results of the standard iterate() function):

#include <cstdio>
#include <string>
using namespace std;

/* Implementation of a binary search tree. Nodes are ordered by key, but also
 * store some data.
 */
struct BinarySearchTree {
  int key;      // they key by which nodes are ordered
  string data;  // the data stored in nodes
  BinarySearchTree *parent, *left, *right;   // parent, left and right subtrees

  /* Initialise the root
   */
  BinarySearchTree(int k, string d, BinarySearchTree *p = NULL)
    : key(k), data(d), parent(p), left(NULL), right(NULL) {};
  /* Insert some data
   */
  void insert(int k, string d);
  /* Searches for a node with the given key. Returns the corresponding data
   * if found, otherwise returns None."""
   */
  string search(int k);
  void iterate();
  void iterate_constant_space();
  void visit();
};

void BinarySearchTree::insert(int k, string d) {
  if (k <= key) { // Insert into left subtree
    if (left == NULL)
      // Left subtree doesn't exist yet, create it
      left = new BinarySearchTree(k, d, this);
    else
      // Left subtree exists, insert into it
      left->insert(k, d);
  } else { // Insert into right subtree, similar to above
    if (right == NULL)
      right = new BinarySearchTree(k, d, this);
    else
      right->insert(k, d);
  }
}

string BinarySearchTree::search(int k) {
  if (k == key) // Key is in this node
    return data;
  else if (k < key && left)   // Key would be in left subtree, which exists
    return left->search(k); // Recursive search
  else if (k > key && right)
    return right->search(k);
  return "NULL";
}

void BinarySearchTree::visit() {
  printf("Visiting node %d storing data %s\n", key, data.c_str());
}

void BinarySearchTree::iterate() {
  visit();
  if (left) left->iterate();
  if (right) right->iterate();
}

void BinarySearchTree::iterate_constant_space() {
  BinarySearchTree *current = this, *from = NULL;
  current->visit();
  while (current != this || from == NULL) {
    while (current->left) {
      current = current->left;
      current->visit();
    }
    if (current->right) {
      current = current->right;
      current->visit();
      continue;
    }
    from = current;
    current = current->parent;
    if (from == current->left) {
      current = current->right;
      current->visit();
    } else {
      while (from != current->left && current != this) {
        from = current;
        current = current->parent;
      }
      if (current == this && from == current->left && current->right) {
        current = current->right;
        current->visit();
      }
    }
  }
}

int main() {
  BinarySearchTree tree(5, "five");
  tree.insert(7, "seven");
  tree.insert(9, "nine");
  tree.insert(1, "one");
  tree.insert(2, "two");
  printf("%s\n", tree.search(3).c_str());
  printf("%s\n", tree.search(1).c_str());
  printf("%s\n", tree.search(9).c_str());
  // Duplicate keys produce unexpected results
  tree.insert(7, "second seven");
  printf("%s\n", tree.search(7).c_str());
  printf("Normal iteration:\n");
  tree.iterate();
  printf("Constant space iteration:\n");
  tree.iterate_constant_space();
}

Answer 4

I think there's no way you could do this, as you should somehow find the nodes where you left off in a path and to identify that you always need O(height) space.

Answer 5

You can do it destructively, unlinking every leaf as you go. This may be applicable in certain situations, i.e. when you don't need the tree afterwards anymore.

By extension, you could build another binary tree as you destroy the first one. You would need some memory micromanagement to make sure that peak memory never exceeds the size of the original tree plus perhaps a little constant. This would likely have quite some computing overhead, though.

EDIT: There is a way! You can use the nodes themselves to light the way back up the tree by temporarily reversing them. As you visit a node, you point its left-child pointer to its parent, its right-child pointer to the last time you took a right turn on your path (which is to be found in the parent's right-child pointer at this moment), and store its real children either in the now-redundant parent's right-child pointer or in your traversal state resp. the next visited children's left-child pointer. You need to keep some pointers to the current node and its vicinity, but nothing "non-local". As you get back up the tree, you reverse the process.

I hope I could make this somehow clear; this is just a rough sketch. You'll have to look it up somewhere (I am sure that this is mentioned somewhere in The Art of Computer Programming).

Answer 6

Pointers from nodes to their ancestors can be had with no (well, two bits per node) additional storage using a structure called a threaded tree. In a threaded tree, null links are represented by a bit of state rather than a null pointer. Then, you can replace the null links with pointers to other nodes: left links point to the successor node in an inorder traversal, and right links to the predecessor. Here is a Unicode-heavy diagram (X represents a header node used to control the tree):

                                         ╭─┬────────────────────────────────────────╮
   ╭─────────────────────────▶┏━━━┯━━━┯━━▼┓│                                        │
   │                        ╭─╂─  │ X │  ─╂╯                                        │ 
   │                        ▼ ┗━━━┷━━━┷━━━┛                                         │
   │                    ┏━━━┯━━━┯━━━┓                                               │
   │               ╭────╂─  │ A │  ─╂──╮                                            │
   │               ▼    ┗━━━┷━━━┷━━━┛  │                                            │    
   │        ┏━━━┯━━━┯━━━┓    ▲         │        ┏━━━┯━━━┯━━━┓                       │
   │      ╭─╂─  │ B │  ─╂────┤         ├────────╂─  │ C │  ─╂───────╮               │
   │      ▼ ┗━━━┷━━━┷━━━┛    │         ▼        ┗━━━┷━━━┷━━━┛       ▼               │  
   │┏━━━┯━━━┯━━━┓ ▲          │   ┏━━━┯━━━┯━━━┓       ▲         ┏━━━┯━━━┯━━━┓        │
   ╰╂─  │ D │  ─╂─╯          ╰───╂   │ E │  ─╂╮      │        ╭╂─  │ F │  ─╂╮       │ 
    ┗━━━┷━━━┷━━━┛                ┗━━━┷━━━┷━━━┛▼      │        ▼┗━━━┷━━━┷━━━┛▼       │
                                    ▲ ┏━━━┯━━━┯━━━┓  │ ┏━━━┯━━━┯━━━┓ ▲ ┏━━━┯━━━┯━━━┓│
                                    ╰─╂─  │ G │   ╂──┴─╂─  │ H │  ─╂─┴─╂─  │ J │  ─╂╯
                                      ┗━━━┷━━━┷━━━┛    ┗━━━┷━━━┷━━━┛   ┗━━━┷━━━┷━━━┛

Once you have the structure, doing an inorder traversal is very, very easy:

Inorder-Successor(p)
    p points to a node.  This routine finds the successor of p in
    an inorder traversal and returns a pointer to that node

    q ← p.right
    If p.rtag = 0 Then
        While q.ltag = 0 Do
            q ← q.left
        End While
    End If

    Return q
    

Lots more information on threaded trees can be found in Art of Computer Programming Ch.2 §3.1 or scattered around the Internet.

Answer 7

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