Trees

[Ian Kelly]

On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody <rustompmody at gmail.com> wrote:
> from enum import Enum
> class TreeTag(Enum):
>     I = 0  # An internal node
>     L = 1  # A leaf node
>     def __repr__(self):  return self.name
>
> I = TreeTag.I
> L = TreeTag.L

Explicitly tagging nodes as internal or leaves is kind of ugly and
also prone to getting out of sync with the reality, which is that a
node is a leaf if it doesn't have any other nodes hanging off of it.

> def dfs(t):
>     if t[0] == L:
>         return [t[1]]
>     else:
>         return [t[1]] + dfs(t[2]) + dfs(t[3])

Over the entire tree, this will do O(n) list additions which implies
O(n) list *copies*, which is rather inefficient. This would probably
be better implemented as a recursive generator.

def dfs(t):
    yield t[0]
    yield from chain.from_iterable(map(dfs, islice(t, 1, None)))

> # Converting to generators is trivial
> =====================

:-)