CODEWITHSUNDEEP
haskellbinary-treeinorder
user6023611
user6023611

Reputation:

Can this implementation of in-order traversal of a binary tree be improved?

I wrote a straightforward in-order-traversal function (toList1) for a binary tree. However, I worry about its complexity (memory / time). Is there a better way to implement it?

data Tree a = Empty | Node a (Tree a) (Tree a) 
toList1 :: (Tree a) -> [a]
toList1 Empty = []
toList1 (Node x lx rx) = (toList lx) ++ [x] ++ (toList rx)

Upvotes: 2

Views: 278

Answers (1)

behzad.nouri
behzad.nouri

Reputation: 78011

Haskell's append ++ performs linearly in the length of its left argument, which means that you may get quadratic performance if the tree leans left. One possibility would be to use difference list.

Another one would be to define a Foldable instance:

data Tree a = Empty | Node a (Tree a) (Tree a)

instance Foldable Tree where
    foldr f z Empty = z
    foldr f z (Node a l r) = foldr f (f a (foldr f z r)) l

then, in-order-traversal comes out naturally:

toList :: Tree a -> [a]
toList = foldr (:) []

and

\> let tr = Node "root" (Node "left" Empty Empty) (Node "right" Empty Empty)
\> toList tr
["left","root","right"]

Upvotes: 3

Related Questions