[Haskell-cafe] Re: Trees
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] Re: Trees
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
Re: [Haskell-cafe] Re: Trees
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
