Paul Rubin at nospam.invalid
Wed Jan 21 02:49:23 CET 2015

Rustom Mody <rustompmody at> writes:
> ## The depth first algorithm
> dfs (L x)   = [x]
> dfs (B x lst rst) = [x]  ++  dfs lst  ++  dfs rst

Cute.  I can't resist posting the similar breadth first algorithm:

bfs (L x)   = [x]
bfs (B x lst rst) = bfs lst  ++ [x] ++  bfs rst

> *Main> dfs t
> [6,2,1,4,3,5,8,7,9]

*Main> bfs t

> The Haskell is bullseye¹ in capturing the essense of a tree because
> conceptually a tree of type t is recursive in the sense that it can contain
> 2 subtrees -- (B x lst rst) -- or its a base case -- L x.

You might like this discussion of a red-black tree implementation whose
datatype makes sure the RB tree invariants are preserved.  The data
definition is kind of verbose, but with more recent GHC versions it can
be made a lot crisper, with datakinds and type-level numeric literals.

More information about the Python-list mailing list