Take the 2-minute tour ×

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.

share|improve this question
I consider link to parent as O(n) auxiliary space. You should edit your question to explicitly mention your binary tree doesn't have such a property. –  LeakyCode Apr 26 '09 at 15:35
How can you not have pointers to your parent nodes? how can you iterate over your tree at all without them? is that where the stack is coming in? you will need parents pointers anyway to do balancing. –  user82238 May 21 '09 at 22:15
add comment

10 Answers

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 ;
share|improve this answer
this destroys the tree though doesn't it? –  Brian R. Bondy Apr 26 '09 at 23:55
No, it just temporarily adds backreferences from certain leaves. –  Svante Apr 27 '09 at 0:01
ah, very nice :) –  Brian R. Bondy Apr 27 '09 at 11:00
This solution is simply amazing. –  Mehrdad Jan 19 '11 at 15:54
Actually, it would be O(n): You only touch a node constant number of times (note that the inner while loop only touches paths that go right and only when curr was the path's leftmost node's parent on entry to the outer while loop; that happens once when you enter the subtree and once you leave it. Then, size of those paths combined = O(size of the whole tree). –  jpalecek Apr 24 '12 at 22:17
add comment

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;
      return NULL;
    if (root->left)
        currentid = 2*currentid;
        root = root->left;
      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);

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");

  printf("\ndoing root2:\n");

  printf("\ndoing root3:\n");

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.

share|improve this answer
Brian, each bit of the number will show you which direction you'd go. –  LeakyCode Apr 26 '09 at 15:54
But how would you access the node #7 for example without using extra space? To recurse to find such a node would take space, and if you stored all nodes in another data structure that would tkae extra space as well. –  Brian R. Bondy Apr 26 '09 at 15:54
@Brian You can subtract 1 and divide by 2 to see that 3 is 7's parent. Likewise, you can subtract 1 and divide by 2 again to see that 1 is 3's parent. Therefore, all you need is a loop that will compute the next step in the path to the desired node from the current node. –  Kyle Cronin Apr 26 '09 at 15:55
@nobody_: your idea is good but you gotta note that it works only in complete binary trees and from a purely theoretical perspective, you still need "O(height) bit" space to store where you were. –  LeakyCode Apr 26 '09 at 15:57
@Mehrdad: I don't understand exactly what you mean with the bits approach, but even if it does make sense.... O(N) = O(C*N). Even if N is 1 bi you still have O(N) space. –  Brian R. Bondy Apr 26 '09 at 16:04
show 9 more comments

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).

share|improve this answer
+1, I commented on this method more with a reference to your answer in my answer. –  Brian R. Bondy Apr 26 '09 at 16:27
Ingenious, but appalling. Just have an up pointer in each element. It is so much simpler, less painful and is well-understood and well-recognized. –  user82238 May 21 '09 at 22:16
add comment

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:

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

    If p.rtag = 0 Then
        While q.ltag = 0 Do
        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.

share|improve this answer
And it's O(n) aux storage ;) –  LeakyCode Apr 26 '09 at 16:28
add comment

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);
      // 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);
      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() {
  if (left) left->iterate();
  if (right) right->iterate();

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

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");
  printf("Constant space iteration:\n");
share|improve this answer
"When you walk back up the tree"... how do you get to the bottom of each node in the tree? –  Brian R. Bondy Apr 26 '09 at 16:10
current = root; while current->left exists: current = current->left –  marcog Apr 26 '09 at 16:17
@marcog: Yes you can surely get to a single node.... But I said how do you get to the bottom of each node in the tree? –  Brian R. Bondy Apr 26 '09 at 16:21
Using the condition I mentioned to go down the right child when you've just come up from the left child. –  marcog Apr 26 '09 at 16:29
And once you process that right child, how do you get the the second left most child? and then the left most's right child? ... You need to store which paths you've taken. –  Brian R. Bondy Apr 26 '09 at 16:31
show 4 more comments

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.

share|improve this answer
You are wrong, Knuth TAOCP I.2.3.1 exercise 21 refers to at least three algorithms for tree traversal in O(1) space without destroying the original tree (although they do modify it temporarily in-place). –  Anton Tykhyy Apr 27 '09 at 5:32
@nobody_: I didn't take into account cases where you are allowed to modify the tree. But I did give 2 examples, so surely it has some :) Anyway I modified my answer to take out the invalid parts. –  Brian R. Bondy Apr 27 '09 at 10:57
For those without TAOCP, @AntonTykhyy is referring to the Morris tree traversal algorithms, which run in O(n) time and O(1) auxiliary space. This page might help: stackoverflow.com/questions/5502916/…. Also, someone posted the pre-order Morris algorithm below. –  John Kurlak Feb 7 '13 at 13:44
add comment

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.

share|improve this answer
add comment


encode your parent node into the leaf pointers

share|improve this answer
add comment

"Datastructures and their algorithms" by Harry Lewis and Larry Denenberg describe link inversion traversal for constant space traversal of a binary tree. For this you do not need parent pointer at each node. The traversal uses the existing pointers in the tree to store path for back tracking. 2-3 additional node references are needed. Plus a bit on each node to keep track of traversal direction (up or down) as we move down. In my implementation of this algorithms from the book, profiling shows that this traversal has far less memory / processor time. An implementation in java is here.

share|improve this answer
add comment

Is it possible to iterate over a binary tree in O(1) auxiliary space.

struct node { node * father, * right, * left; int value; };

This structure will make you be able to move 1-step in any direction through the binary tree.
But still in iteration you need to keep the path!

share|improve this answer
add comment

Your Answer


