Re: Tomazos Binary Tree Traverse Algorithm

On Nov 10, 10:09 pm, "Paul E. Black" <p.bl...@xxxxxxx> wrote:
On Monday 10 November 2008 05:37, and...@xxxxxxxxxxx wrote:





Tomazos Binary Tree Traverse Algorithm

Andrew Tomazos <and...@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.

Yes, a number of people have mentioned that it requires an O(1)
Parent[N] function to work. I know a subset of trees have this
facility (redblack trees, btrees, heaps, trees stored in arrays (ie
parent(i) = i/2)).

Thats a cool idea about reusing the child pointers to temporarily be
parent pointers, I hadn't thought of that. You would have to turn
off read access while iterating it, and make sure you aren't
interrupted half way through and leave the tree in a corrupted state.
-Andrew.

.

Relevant Pages

  • Re: Tomazos Binary Tree Traverse Algorithm
    ... We describe an algorithm that traverses a binary tree in Otime and ... Your algorithm works nicely. ... Traversal Algorithm for Binary Trees with Parent Pointers. ...
    (comp.theory)
  • Re: Singly Linked LIst and Objects Newbie Question
    ... Hm it seems that my algorithm and datastructure knowledge is really ... I had never even heard of red-black trees or 2-3-4 trees or any ... So for example you want to write an assertion that evaluates a complex ... boolean method1_checkAssert{ ...
    (comp.lang.java.programmer)
  • Re: No trees in the stdlib?
    ... The particular algorithm to achieve this is a secondary issue. ... It's my fault for having opened the topic with simply "trees" instead, it would have avoided this vagueness problem, but I'm genuinely surprised to know there are no data structures that efficiently support such a common need in Python. ... second option, anyway) ...
    (comp.lang.python)
  • Re: A Definition of an Algorithm
    ... Towards a Definition of an Algorithm ... the set of primitive recursive functions is considered. ... trees that show how the function is built up. ... a language built with binary trees is fundamentally different ...
    (sci.math.research)
  • Re: help: a O(n) algorithm to find the longest path in a tree
    ... Note also that by performing a DFS in trees from a node a0 you can ... iteratively) is equal to the distance. ... The algorithm runs a slightly modified DFS twice, ...
    (comp.theory)
Loading