# Trees

Rustom Mody rustompmody at gmail.com
Tue Jan 20 19:15:58 CET 2015

```On Tuesday, January 20, 2015 at 10:51:13 PM UTC+5:30, Ian wrote:
> On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody  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.

Yeah...

Just demoing a technique for more variegated trees eg
an AST for some toy DSL or some such.
Imagine you have 10 types of nodes and one defaults to tagless

>
> > 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.

Yeah

>
> def dfs(t):
>     yield t[0]
>     yield from chain.from_iterable(map(dfs, islice(t, 1, None)))
>
> > # Converting to generators is trivial
> > =====================
>
> :-)

Less trivial than I thought...
Why does this not work?

def dfsg(t):
if t[0] == L:
yield t[1]
else:
yield from dfsg(t[2])
yield from dfsg(t[3])

```

More information about the Python-list mailing list