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

@Jim Balter: not homework, I wish. I'm 17 and still stuck in high-school (or at least the Dutch version of it). It's for a Python project, and it is used in an iterator. — orlp, Dec 15 '11 at 10:44
@Gumbo: Woops, forgot to say that in the question. I want to visit each node once, and if possible in order (from the mostleft to the mostright node). — orlp, Dec 15 '11 at 10:47
Again, what have you tried? Surely you can at least find your way to the first (leftmost) node ... figure out what to do next. — Jim Balter, Dec 15 '11 at 10:49
How can iterating over a structure with `n` elements ever be more time-efficient than `O(n)`?! — ThiefMaster, Dec 15 '11 at 10:50
@ThiefMaster: In space it's possible and even pretty easy. In time, you are right. — thiton, Dec 15 '11 at 10:52
@ThiefMaster: O(1) __space__, which means the algorithm uses a constant amount of memory, where an algorithm of O(n) __space__ uses an amount of memory linear to the the amount of elements. You are confusing space with execution speed. — orlp, Dec 15 '11 at 10:53
@Jim Balter: I have only thought of (trivial) recursive solutions, and replacing that recursion with an explicit stack, but I can't seem to think of a solution that doesn't keep track of visited nodes somehow. — orlp, Dec 15 '11 at 10:54
@Thief I made the same mistake in my head and have tried to pre-empt anyone else suffering with an edit :) — AakashM, Dec 15 '11 at 10:54
@nightcracker Did you think of, um, searching the web, even searching SO? http://stackoverflow.com/questions/791052/iterating-over-a-binary-tree-with-o1-auxiliary-space — Jim Balter, Dec 15 '11 at 11:00
Your struct does not compile as it is, because the typedefed `Node` is not useable inside your struct. Use: `typedef struct Node { struct Node *parent;...} Node;` instead. — halex, Dec 15 '11 at 13:29
@halex: Oh, I just wrote a pageholder on this quest, it wasn't meant to compile. — orlp, Dec 15 '11 at 15:20

score 8 · Accepted Answer · answered Dec 15 '11 at 10:57

8

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.

answered Dec 15 '11 at 10:57

thiton

35,651
4
70
100

Of course! And this allows me to iterate over the tree in order by starting with the leftmost's-parent node and the last node set to the leftmost node. Thanks! – orlp Dec 15 '11 at 10:59
@nightcracker You can iterate over the tree by starting with the root node and the last node set to NULL (the root node's parent). – Jim Balter Dec 15 '11 at 11:13

score 0 · Answer 2 · answered Nov 03 '13 at 07:41

"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 (c would be faster i guess) is here.

Ambroz Bizjak · Answer 3 · 2011-12-15T11:08:25.727

0

It is possible to get the next in-order node given a pointer to some node, as long as you keep parent pointers. This can be used to iterate the tree, starting with the leftmost node. From my implementation of AVL tree:

BAVLNode * BAVL_GetNext (const BAVL *o, BAVLNode *n)
{
    if (n->link[1]) {
        n = n->link[1];
        while (n->link[0]) {
            n = n->link[0];
        }
    } else {
        while (n->parent && n == n->parent->link[1]) {
            n = n->parent;
        }
        n = n->parent;
    }

    return n;
}

To get the leftmost node:

BAVLNode * BAVL_GetFirst (const BAVL *o)
{
    if (!o->root) {
        return NULL;
    }

    BAVLNode *n = o->root;
    while (n->link[0]) {
        n = n->link[0];
    }

    return n;
}

Here, node->link[0] and node->link[1] are the left and right child of the node, respectively, and node->parent is the pointer to the parent node (or NULL for root).

A single GetNext() operation has O(logn) time complexity. However, when used to iterate the entire tree, you get O(n) amortized time complexity.

edited Dec 15 '11 at 11:08

answered Dec 15 '11 at 11:02

Ambroz Bizjak

7,809
1
38
49

This doesn't work. For instance, it returns NULL for any tree where the root has no right link.... Well, maybe it works with your edit, starting at the leftmost node. – Jim Balter Dec 15 '11 at 11:18
It *does* work. If you call GetNext(root) and the root has no right link, then yes, it returns NULL - because the root is the *last node*, and there is no next node. An if you call GetNext(rightmost child of root's left child), it retuns the root (not NULL). Also, I've used that code in like 20 different places with no issues. – Ambroz Bizjak Dec 15 '11 at 11:27
@Jim: obviously you have to start at the leftmost node, not the root, in order to iterate the tree in-order. – Ambroz Bizjak Dec 15 '11 at 11:28
That is NOT obvious. See, for instance, thiton's answer and my comment on it. – Jim Balter Dec 18 '11 at 08:20
@Jim: I mentioned at the beginning of my answer that GetNext() returns the next *in-order* node of the given node. It follows from this that you have to start with the node having least value, i.e. leftmost, in order to get all the nodes with repeated invocation of GetNext(). It's obvious the same way as it is that to iterate a *linked list* from start to finish, you have to start at the first node, not some middle node. – Ambroz Bizjak Dec 18 '11 at 09:23
@Jim: also see how my way is generally more useful than thiton's, since it iterates *in-order*, which is needed in many cases. E.g. if you inserted integers into the tree, you can sort them just iterating the tree in-order. – Ambroz Bizjak Dec 18 '11 at 09:25

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

3 Answers3