Re: Tomazos Binary Tree Traverse Algorithm

On Monday 10 November 2008 05:37, andrew@xxxxxxxxxxx wrote:
Tomazos Binary Tree Traverse Algorithm

Andrew Tomazos <andrew@xxxxxxxxxxx> <http://www.tomazos.com>
2008-11-10

Abstract

We describe an algorithm that traverses a binary tree in O(n) time and
O(1) space. Each node is visited exactly three times, once preorder,
once inorder and once postorder. We provide a conceptual description,
an implementation in C and the sketch of a proof.

It is possible to simulate this journey only keeping local
information:

1. The current castle
2. Which of the three important sides (WEST, SOUTH, EAST) we are on of
the current castle.

while (p != NULL) {
if (state == west) {
visit_preorder(p);

if (p->left_child)
p = p->left_child;
else
state = south;
}

if (state == south) {
visit_inorder(p);

if (p->right_child) {
p = p->right_child;
state = west;
}
else
state = east;
}

if (state == east) {
visit_postorder(p);

if (p->parent) {
if (p == p->parent->left_child)
state = south;
else // p == p->parent->right_child
state = east;
}

p = p->parent;
}
}

Andrew,

Your algorithm works nicely.

I consider it confusing to say that the algorithm take Theta(1)
space. Your binary tree data structure requires every node to have a
pointer to its parent, which is not typical. I suggest characterizing
the algorithm as needing Theta(n) space or calling it something like
Traversal Algorithm for Binary Trees with Parent Pointers.

One can write an algorithm to do the same traversal in a binary tree
without parent pointers and really use constant space. The trick is
to reverse pointers on the way down, so you can find your parent, then
reverse them again on the way up to restore them to their initial
state.

-paul-

.

Relevant Pages

  • Re: Suitable Data Structure?
    ... >implement the following algorithm effectively: ... The precise components jof v that will ... >Simply selecting the largest element in requires Ooperations, ... >course, O, which could be obtained if a binary tree could be used. ...
    (sci.math.num-analysis)
  • Monotone Decomposition
    ... It's the first step in the classic Otriangulation algorithm. ... During the plane-sweep some of the active edges are stored in a binary tree or similar Osearch-structure. ... I have no idea how the search for the rightmost edge should work. ... The only reliable way to get the rightmost intersection-point seems to calculate the intersections and compare them. ...
    (comp.graphics.algorithms)
  • Re: Tomazos Binary Tree Traverse Algorithm
    ... I consider it confusing to say that the algorithm take Theta ... Traversal Algorithm for Binary Trees with Parent Pointers. ... One can write an algorithm to do the same traversal in a binary tree ...
    (comp.theory)
  • Suitable Data Structure?
    ... implement the following algorithm effectively: ... The precise components jof v that will ... Simply selecting the largest element in requires Ooperations, ... course, O, which could be obtained if a binary tree could be used. ...
    (sci.math.num-analysis)
  • Re: Binqry Tree sort
    ... Actually I'm looking for a parallel proessing, ... The connection between processors are like the binary tree. ... The parent processor compares the ... Now I'm looking for a parallel algorithm wich uses parallel binary tree ...
    (comp.programming)