0

I have this function that i wrote to pass from a tree to a list in Haskell:

treeToList :: Tree -> [Int]
treeToList (Leaf x) = [x]
treeToList (Node left x right) =  treeToList left ++ [x] ++ treeToList right

This works just fine, however i have a doubt:

With the input: 

treeToList (Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5)))

the function produces this list:

[1,2,3,4,5]

which, i think is wrong, because if i want to go the other way around, and write the tree from the list, i'm going to write it wrong.

How can i fix this ?

laker001
  • 417
  • 7
  • 20
  • It's not obvious what you mean by "write wrong". There are many ways we can turn a list into a tree (while keeping elements in order). Also, if you want to "go the other way", you'll have to write an entirely different function, so I don't see why this `treeToList` is relevant to that. – András Kovács Jan 17 '15 at 12:33
  • It is not possible to go the other way around: any tree visit (pre-, post-,in-) defines a non-injective map from trees to lists, so information is lost. At bast, you can achieve a pseudo-inverse, i.e. reconstructing one of the many trees which once visited give the input list back. – chi Jan 17 '15 at 12:34
  • @AndrásKovács so this is a correct way of transforming a tree into a list ? – laker001 Jan 17 '15 at 12:42
  • @laker001 Yes. This is an [in order traversal](http://en.wikipedia.org/wiki/Tree_traversal#In-order_.28symmetric.29) of a tree. It is perfectly valid. – ThreeFx Jan 17 '15 at 13:11
  • For a given _n_ you have many possible shapes of an _n_-element binary tree, but just one list. So there is no way how to go back without additional information. See [With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?](http://stackoverflow.com/q/3042412/1333025). – Petr Jan 17 '15 at 17:19

1 Answers1

1

This is a correct way to transform a binary tree of Int into a list by "in-order" traversal. This is the most common way to turn a search tree into a list. There are, however, other valid ways to traverse trees which will produce lists in different orders for various purposes, as you can see on Wikipedia. As András Kovács and chi have indicated, there is generally no way to go backwards, unless you have specific information about the shape of the tree you wish to construct.

dfeuer
  • 48,079
  • 5
  • 63
  • 167