Browse Groups

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

(12)
• NextPrevious
• 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
Message 1 of 12 , Aug 25, 2005
View Source
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
• ... You are relying on the existance of Node.OldestChild(), Node.NextSibling() and Node.Parent(). Implementing these, you ll discover that it s impossible
Message 1 of 12 , Aug 25, 2005
View Source
On 25/08/05, Omer Zak <omerz@...> wrote:
> 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.

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
• ... 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
Message 1 of 12 , Aug 25, 2005
View Source
On Thu, 2005-08-25 at 11:25 +0300, guy keren wrote:
> 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?).

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

> this implies that your algorithm is not re-entrant (can't have to
> 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.

On Thu, 2005-08-25 at 00:39 -0700, Arik Baratz wrote:
> On 25/08/05, Omer Zak <omerz@...> wrote:
> > 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.
>
> 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.

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

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

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

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

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

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/

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
• ... 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
Message 1 of 12 , Aug 25, 2005
View Source
On 25/08/05, Omer Zak <omerz@...> wrote:

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

> 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

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
• ... 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?).
Message 1 of 12 , Aug 25, 2005
View Source
On Thu, 25 Aug 2005, Omer Zak wrote:

> 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?

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

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

--
guy

"For world domination - press 1,
or dial 0, and please hold, for the creator." -- nob o. dy
• ... Continuing the argument by shouting match: NO! NO!! NO!!! This is recursion because I am shouting louder than you!!!! ... When the tree is really immutable
Message 1 of 12 , Aug 25, 2005
View Source
On Thu, 2005-08-25 at 01:16 -0700, Arik Baratz wrote:
> On 25/08/05, Omer Zak <omerz@...> wrote:
>
> > > 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.
> >
> > 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.

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

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

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

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
• ... 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
Message 1 of 12 , Aug 25, 2005
View Source
On 25/08/05, Omer Zak <omerz@...> wrote:
> - 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.

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
• ... 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.
Message 1 of 12 , Aug 25, 2005
View Source
On Thu, 25 Aug 2005, Arik Baratz wrote:

> On 25/08/05, Omer Zak <omerz@...> wrote:
> > - 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.
>
> 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...

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

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

"For world domination - press 1,
or dial 0, and please hold, for the creator." -- nob o. dy
• ... 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
Message 1 of 12 , Aug 25, 2005
View Source
On Thu, 2005-08-25 at 16:33 +0300, guy keren wrote:
> On Thu, 25 Aug 2005, Arik Baratz wrote:
>
> > On 25/08/05, Omer Zak <omerz@...> wrote:
> > > - 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.
> >
> > 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...
>
> 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
>
> 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.

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)

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.

> 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

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/

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
• [... snipped ...] 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
Message 1 of 12 , Aug 25, 2005
View Source
[... snipped ...]
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
^^^^^^ should be "edge"
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)

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.
[... snipped ...]
--- 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/

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
• ... 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]
Message 1 of 12 , Aug 25, 2005
View Source
On Fri, 26 Aug 2005, Omer Zak wrote:

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

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

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

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

> > 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
>
> 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?

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

"For world domination - press 1,
or dial 0, and please hold, for the creator." -- nob o. dy
• ... How about that what-is-its-name transformation, which establishes an equivalence relationship between general and binary trees? Then you need to deal only
Message 1 of 12 , Aug 25, 2005
View Source
On Fri, 2005-08-26 at 02:13 +0300, guy keren wrote:

> 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),
> then. (if this operation is not O(1), it makes your scanning algorithm
> 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.

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

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.

> 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?

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/

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
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.