Linear Time Tree Traversal Generator

[justin walters]

On Tue, Sep 20, 2016 at 9:46 AM, ROGER GRAYDON CHRISTMAN <dvl at psu.edu>
wrote:

> I am trying to find a better (i.e. more efficient) way to implement a
> generator
> that traverses a tree.
>
> The current model of the code (which is also used by a textbook I am
> teaching
> from does this)
>
>    def __iter__(node):
>          for x in iter(node._left):
>               yield x
>          yield node._value
>          for x in iter(node._right)
>               yield x
>
> This is nice, simple, and straightforward, but has an O(n log n) running
> time,
> since
> values from the leaves of the tree have to be yielded multiple times to
> the top
> of the tree.
>


Are the left and right attributes collections of more nodes or are they
simply references to the node's position in the tree?

>From the code provided it seems like the former is true and a node's left
attribute is a reference to another node?

I don't know how flexible you are with the structure of your tree, but you
could try taking the modified pre-order tree traversal approach.

This article explains it in the context of a database, but the idea is the
same: https://www.sitepoint.com/hierarchical-data-database-2/

Each node would then have a parent attribute as well as left and right
attributes. The parent would be a reference to a parent node, and the left
and right would be integers that position the element in the tree.

The upside to this is that traversal and lookup is much faster since you do
not need to have an iterator nested in an iterator. This is because the top
level node will always have the lowest integer as it's left attribute and
the highest integer as it's right attribute. That means that you can
instead have a single iterator that iterates through a range of integers to
yield the node with the specified left and right values.

The downside is that inserting a new node can take a long time because,
depending on the insertion point, the left and right values for each node
in the tree may have to be recalculated.

Now, I may have completely missed the mark here. I am completely self
taught and have only been programming for about 3 years. I hope that you
gleaned some value from my response either way.