Trees

[Rustom Mody]

On Thursday, January 22, 2015 at 3:57:50 AM UTC+5:30, Paul Rubin wrote:
> Rustom Mody  writes:
> > Thats not bfs. That's inorder traversal
> 
> Oops, you're right.  How's this:
> 
> bfs x = go [x] where
>   go [] = []
>   go (L x:ts) = x:go ts
>   go (B x lst rst:ts) = x : go (ts ++ [lst, rst])
> 
> *Main> bfs t
> [6,2,8,1,4,7,9,3,5]

Yeah thats right.
And now you can get the duality between dfs and bfs you were earlier after by
replacing the 
ts ++ [lst,rst]
with
[lst,rst] ++ ts

BTW this is just converting queue to stack;
And its neat; and out of reach of those who think only imperatively

PS
1. Ive not tried it
2. For n-ary trees its neater
3. In my imaginary language with first-class sets, bags, lists it would be neater still