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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
