Iterating over AVL tree in O(1) space without recursion

Question

I have an AVL Tree. Each node looks like this:

typedef struct {
    Node *parent;  // the parent node
    Node *left;    // the node left of this node
    Node *right;   // the node right of this node
    int height;    // the height of this node
    void *value;   // payload
} Node;

Is it possible to iterate over an AVL tree with these nodes in O(1) space, without recursion, if yes, how?

If not, a solution with sub-O(n) space or iff really necessary O(N) space is appreciated as well.

With iterating over the tree I mean I want to visit each node once, and if possible in order (from the mostleft to the mostright node).

Answer 1

If you store the last node you have visited, you can derive the next node to visit in an iterator.

• If the last node was your parent, go down the left subtree.
• If the last node was your left subtree, go down the right subtree.
• If the last node was your right subtree, go to your parent.

This algorithm gives you a traversal in O(1) for the tree. You need to flesh it out a little for the leaves and decide what kind of iterator (pre/in/post-order) you want to decide where the iterator should and wait for incrementation.