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.
Bob
On 3 Dec 2007, at 08:40, apfelmus wrote:
Adrian Neumann wrote:
> data Tree a = Leaf a | Node a [Tree a]
But now the assignments require more than a simple top-down
traversal. For example: given a tree t and two nodes u,v, find the
first common ancestor.
Well, this problem doesn't make much sense in Haskell. How do you
specify the subtrees u and v in the first place?
Regards,
apfelmus
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe