[Haskell-cafe] Re: Trees

[apfelmus]

Thomas Davie wrote:
> apfelmus wrote
>> Well, this problem doesn't make much sense in Haskell.
>> How do you specify the subtrees u and v in the first place? 
>
> One could alway store a node's depth at each node -- then you must 
> search for u and v, creating a list of what nodes you found at each 
> depth, and finally, simply compare the lists -- O(n) in the depth of u 
> and v.

Huh? I mean, are u and v node labels of type a? Or are they subtrees? In 
any case, they aren't "pointers" into the tree.

In the case of node labels, a breath first search will take

   O(number of nodes of depth <= min (depth u) (depth v))

steps which is

   O(size of the tree)

in the worst case.


Regards,
apfelmus