Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!bcyclone04.am1.xlned.com!bcyclone04.am1.xlned.com!newsfeed.xs4all.nl!newsfeed3a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <d34dbfbe-fe82-47dc-8bc3-c8773e2b70dd@googlegroups.com>
References: <CAG=hEY1L-39EmuWpdEh_n-BNfs=qG9nL=MrMT0ar72yGBrkoUA@mail.gmail.com> <mailman.17884.1421734095.18130.python-list@python.org> <d34dbfbe-fe82-47dc-8bc3-c8773e2b70dd@googlegroups.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Tue, 20 Jan 2015 10:19:40 -0700
Subject: Re: Trees
To: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.17892.1421774424.18130.python-list@python.org>
Lines: 32
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:84074

On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody <rustompmody@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
> =====================

:-)