Subject: Question to graph theorists - non-recursive binary tree traversal algorithm?

From: Omer Zak <[email-masked]>
Date: Thu, 25 Aug 2005 10:29:39 +0300

I devised an algorithm for traversing a tree, which does not need to
maintain a stack.  Is the algorithm a familiar one?  If not, does it
have any flaw?

The algorithm is as follows.
1. Initially:
   Node <- pointer to tree's root node
   Direction <- downward
2. Visit Node.
   If Direction==downward, go to 3.
   Otherwise, go to 4.
3. If Node has children,
     Node <- Node.OldestChild(), go to 2.
   Otherwise, if Node has a younger sibling,
     Node <- Node.NextSibling(), go to 2.
   Otherwise,
     Direction <- upward, go to 4.
4. If Node==pointer to tree's root node, terminate.
   Otherwise, Node <- Node.Parent().
   If Node has a younger sibling,
     Node <- Node.NextSibling(), Direction <- downward, go to 2.
   Otherwise, go to 4.

The above algorithm implements depth-first, prefix order of visiting the
tree's nodes.
It may be possible to modify the algorithm to implement infix order or
postfix order by moving the Visit Node statement to other places in the
algorithm, but I did not investigate it.

To implement a breadth-first tree traversal algorithm (i.e. all nodes at
level N are visited before visiting a node at level N+1), it may be
sufficient to maintain a counter remembering the current level and
determine for each visited node which level it belongs to - so only
nodes at the current level are actually manipulated.
                                                  --- Omer
-- 
Every good master plan involves building a time machine.  Moshe Zadka
My own blog is at http://www.livejournal.com/users/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.html

---

From: Arik Baratz <[email-masked]>
Date: Thu, 25 Aug 2005 00:39:08 -0700

>      Direction <- upward, go to 4.

You are relying on the existance of Node.OldestChild(),
Node.NextSibling() and Node.Parent(). Implementing these, you'll
discover that it's impossible (especially NextSibling() and Parent())
without some information regarding a node's sibling or at least a
node's parent in the node. This information replaces the information
usually found in the stack in the regular recursive DFS.

There are other ways to DFS without recursion, a notable one is to
hold a linked list of pointers to the nodes above the current one,
starting with the lowest, building it as you go by always adding to
the head, and when you exhaust a node you simply remove the last link
in the list. This is in fact uses the linked list as a stack.

Then there's a question of why you want to avoid the recursion in the
first place. It is more efficient than the methos you suggest - your
suggestion requires O(n) space in all cases, while the stack, be it
the language stack or a stack you are implementing, requires O(log n)
space if the tree is balanced (and O(n) if it is very unbalanced).

-- Arik

---

From: guy keren <[email-masked]>
Date: Thu, 25 Aug 2005 11:25:57 +0300 (IDT)

On Thu, 25 Aug 2005, Omer Zak wrote:

> maintain a stack.Is the algorithm a familiar one?  If not, does it
> have any flaw?

no, except that instead of using a stack, you are storing the information
inside the nodes (i.e. how would the 'Node.NextSibling' method work
otherwise?).

this implies that your algorithm is not re-entrant (can't have to
different threads running it simultaneously, for example). it also implies
that you rely on extra data stored in the nodes at all times.

omer, you appear to be in a wierd mood today. i am waiting now for your
attempt at solving the solvability(?) problem ;)

--guy

-- 
guy

"For world domination - press 1,
 or dial 0, and please hold, for the creator." -- nob o. dy

---

From: Omer Zak <[email-masked]>
Date: Thu, 25 Aug 2005 11:00:36 +0300

> inside the nodes (i.e. how would the 'Node.NextSibling' method work

Very true.  My algorithm requires each node to have also a pointer to its parent.
A pointer to the next sibling is optional (but if it is missing and the tree is not
binary, then the algorithm is less efficient).

> different threads running it simultaneously, for example).

Not true.  The various links are read only, not written.  Mutable state is stored
in the algorithm's process and consists of pointer to current node and traversal
direction flag.

> usually found in the stack in the regular recursive DFS.

Yes.  Also Guy Keren pointed this out (see above).

> in the list. This is in fact uses the linked list as a stack.

In my book, this is recursion using a different name.

> space if the tree is balanced (and O(n) if it is very unbalanced).

Guy made an incorrect comment about reentrancy, but since my algorithm
is reentrant, I can suggest one possible application in which my
algorithm would be better than a recursive algorithm:

When you have 2^10 processes running simultaneously, and each one of
them needs to traverse the tree, then my algorithm requires exactly two
storage cells per process (one for pointer, one for Boolean flag).  The
various links, being read-only, are shared between all processes.

In a recursion/linked list based algorithm, each process needs to
maintain its own stack of pending node pointers.
                                              --- Omer
-- 
Every good master plan involves building a time machine.  Moshe Zadka
My own blog is at http://www.livejournal.com/users/tddpirate/

---

From: Arik Baratz <[email-masked]>
Date: Thu, 25 Aug 2005 01:16:00 -0700

> In my book, this is recursion using a different name.

No. Recursion is when you use recursion. :-)

Recursion is when you use the language's stack to hold data for you.
Using a user data structure does not constitute (at least in my mind)
a recursive algorithm. It's an iterative algorithm utilizing a stack.

> various links, being read-only, are shared between all processes.

Then I'll ask another question, if I may: If all those m processes
need access to the same data in the same order, won't it be easier to
unroll the tree into a linear structure, which also  requires O(n)
space, such as a linked list, and then traverse it with the processes
instead of re-traverse the binary tree again and again? Just a
thought.

-- Arik

---

From: Omer Zak <[email-masked]>
Date: Thu, 25 Aug 2005 11:30:53 +0300

> a recursive algorithm. It's an iterative algorithm utilizing a stack.

Continuing the argument by shouting match:
NO! NO!! NO!!!
This is recursion because I am shouting louder than you!!!!
:-) :-) :-) :-) :-)

> instead of re-traverse the binary tree again and again? Just a

When the tree is really immutable or is modified only rarely, your
suggestion is indeed easier.

However, what happens if some (or all) of the assumptions are incorrect:

- Processes need to access the tree in different orders (prefix vs.
postfix traversal, for example)?
- Processes need to skip different parts of the tree while traversing
it.
- The tree is dynamically modified by another process (stipulating that
there are locking mechanisms such that processes in middle of tree
traversal are not confused by the change) and it is expensive to unroll
the tree after each modification.

In short:  the tradeoffs of the algorithm, which I suggested, are such
that is useful under certain circumstances, which are probably rare in
practice.
My real question - was this algorithm, or a similar algorithm, already
proposed by someone else?
                                       --- Omer
-- 
Every good master plan involves building a time machine.  Moshe Zadka
My own blog is at http://www.livejournal.com/users/tddpirate/

---

From: Arik Baratz <[email-masked]>
Date: Thu, 25 Aug 2005 01:51:36 -0700

> the tree after each modification.

Hm.. I just came back from my thinking place, and it seems to me like
Guy may be right after all. Your NextSibling() node method needs to
know what you mean by 'next', so it has to somehow remember where in
relation to other siblings you are now. It has to go to the parent,
and look for the 'next' sibling. You need to keep information
regarding which is the next sibling somewhere, and that somewhere is
different for each process...

> proposed by someone else?

If I were you I'd open a good old algorithms reference and look for
graph traversal algorithms, you might come across something familiar.

-- Arik

---

From: guy keren <[email-masked]>
Date: Thu, 25 Aug 2005 16:33:04 +0300 (EET DST)

> different for each process...

ofcourse i was right. omer had tried to show that some basic issues of
computation theory are wrong, or some very hard problems are actually
easy to solve. what are the chances of him being right about this?

you cannot traverse a tree using an O(1) ammount of extra memory - i think
if omer looks properly, he'll find proofs for this theorem.

as i said, omer's in a very strange mood today - it's not like him to come
up with so many fataly flawed ideas. could it be that someone took over
omer's email account and is trying to ruin his reputation? :0

-- 
guy

---

From: Omer Zak <[email-masked]>
Date: Fri, 26 Aug 2005 01:11:38 +0300

> if omer looks properly, he'll find proofs for this theorem.

If the tree nodes have links to their siblings and parents, and if the
memory occupied by the links is not counted as extra memory (reasonable
when the trees are read-only accessed by several processes, each of
which needs to maintain its own traversal state) - then you can consider
the tree as a maze (each vertex is a corridor and each node is a meeting
place of few corridors).  You then follow the maze using the right hand
law.  When using the right hand law, you do not need more than O(1)
read-write memory.

Of course, when only a single process needs to traverse the tree at the
same time, it is more economical to maintain the O(log N) read-write
memory than to spend space on redundant links in the tree.

> omer's email account and is trying to ruin his reputation? :0

Thanks for the belated compliment on my past ideas.
If you feel bored by my flawed but nevertheless interesting (at least to
my ego) ideas, which were publicized in an attempt to wake up the
Hackers-IL mailing list, can you post your own speculative (translation:
flawed) but interesting ideas?
                                           --- Omer
-- 
Jara Cimrman!  He is one of the unsung geniuses--scientist, engineer,
inventor and literary critic.
My own blog is at http://www.livejournal.com/users/tddpirate/

---

From: Omer Zak <[email-masked]>
Date: Fri, 26 Aug 2005 01:14:29 +0300

[... snipped ...]
                         ^^^^^^ should be "edge"

[... snipped ...]

---

From: guy keren <[email-masked]>
Date: Fri, 26 Aug 2005 02:13:37 +0300 (IDT)

On Fri, 26 Aug 2005, Omer Zak wrote:

> place of few corridors).You then follow the maze using the right hand
> law.When using the right hand law, you do not need more than O(1)
> read-write memory.

aha, but you are forgetting that you do not have an upper-bound on the
number of children for a given node. consider this:

                  [ P ]

  [C1]  [C2]  [C3]   [C4]   [C5]  [C6] [C7]  [C8]  [C9]  [C10]  [C11]

lets say we were in C2, and are now returning to P. we now need to find
which is the next node we should visit. the only way to make this in O(1),
is that each node will keep a link to its sibling. add these links too,
then. (if this operation is not O(1), it makes your scanning algorithm
less efficient then O(N)).

if you'll want to scan the tree in reverse order, you'll need the siblings
list to be bidirectional.

if you'll want to make a BFS scan, rather then DFS.....

so, you see, you're creating a tree that lends itself to one manner of
traversal, and does not work for other types of traversals.

this could be useful for specific types of problems, ofcourse, but this is
not the generic issue of traversing a tree structure.

> memory than to spend space on redundant links in the tree.

log N is relevant assuming a balanced tree. in fact, it's not log N, but
log (largest number of children of a single parent).

> flawed) but interesting ideas?

if you can't bring up something useful - it's better to keep the list
quiet. would you like me to bring up my mission-imposible project of
devising an algorithm that automatically translates C programs into C++
programs while introducing classes based on usage relations between data
and functions in the original C program?

-- 
guy

---

From: Omer Zak <[email-masked]>
Date: Fri, 26 Aug 2005 03:02:11 +0300

> less efficient then O(N)).

How about that what-is-its-name transformation, which establishes an
equivalence relationship between general and binary trees?

Then you need to deal only with two children per node.

> not the generic issue of traversing a tree structure.

OK, I give up.
I propose a bicycle as a transportation vehicle, pointing out that it is
the best solution for some specialized transportation situations.
You reply by reminding us that most of the transportation needs of
humans are better served by cars and airplanes.

> and functions in the original C program?

Sounds cool and interesting.  Can you tell us more about it?
How do you avoid the trivial solution of enclosing function declarations
by extern "C" { ... } declarations?
                                                    --- Omer
-- 
Every good master plan involves building a time machine.  Moshe Zadka
My own blog is at http://www.livejournal.com/users/tddpirate/